{"id":280,"date":"2011-08-23T15:48:53","date_gmt":"2011-08-23T19:48:53","guid":{"rendered":"http:\/\/wcarss.ca\/log\/?p=280"},"modified":"2011-11-08T01:02:11","modified_gmt":"2011-11-08T06:02:11","slug":"a-nice-way-to-generate-all-subsets-within-python","status":"publish","type":"post","link":"https:\/\/wcarss.ca\/log\/2011\/08\/a-nice-way-to-generate-all-subsets-within-python\/","title":{"rendered":"A nice way to generate all subsets within python."},"content":{"rendered":"<p>Disclaimer: this post has some lousy code and a serious factual error. Throughout, I am speaking about a method of generating all permutations of a set, while saying that I&#8217;m speaking about generating all subsets of a set! I have written a <a href=\"http:\/\/wcarss.ca\/log\/2011\/11\/correction-i-do-know-what-subsets-are-i-swear\/\" title=\"fixed this for me\">newer post<\/a> which integrates content from a comment by <a href=\"http:\/\/codex.grimoire.ca\/\" title=\"good reading\">Owen Jacobson<\/a>, along with a short response explaining just what the heck I was thinking. This post has been left intact aside from this disclaimer for the sake of posterity!<\/p>\n<p>Recently on hackernews, I saw <a title=\"jiminy jilickers!\" href=\"http:\/\/stackoverflow.com\/questions\/1218390\/what-is-your-most-productive-shortcut-with-vim\/1220118#1220118\">this amazing bunch of vimfu<\/a> (learned some nifty tricks from it too!), and so I went to check out Jim Dennis&#8217; <a title=\"why are you looking for a link title on this?\" href=\"http:\/\/stackoverflow.com\/users\/149076\/jim-dennis#qpage_1-anpage_1-qsort_votes-ansort_votes\">other answers<\/a>. Nothing quite so popular, but some worthy reads about &#8220;<a href=\"http:\/\/stackoverflow.com\/questions\/1731152\/job-requirements-what-does-kernel-developer-really-mean\">what qualifies a person as a kernel developer<\/a>&#8221; and &#8220;<a href=\"http:\/\/stackoverflow.com\/questions\/1774920\/can-i-use-a-shared-library-compiled-on-ubuntu-on-a-redhat-linux-machine\/1775035#1775035\">can I run a .so compiled in red hat under ubuntu?<\/a>&#8221; &#8211; the one that inspired this post though, is the classic &#8220;<a href=\"http:\/\/stackoverflow.com\/questions\/4074991\/generate-all-permutations-of-all-lengths\/4075028#4075028\">how to generate all subsets of a set?<\/a>&#8221;<\/p>\n<p>Jim suggests using python&#8217;s <a href=\"http:\/\/docs.python.org\/library\/itertools.html\">itertools<\/a>\u00a0module (in addition to bitmasking on the subset-representation), and I&#8217;ve never had cause to look at itertools before. Boy, how I wish I had! I quickly whipped up the following (after reading about <a href=\"http:\/\/docs.python.org\/tutorial\/controlflow.html#arbitrary-argument-lists\">argument packing\/unpacking<\/a>:<\/p>\n<script src=\"https:\/\/gist.github.com\/1166285.js\"><\/script><noscript><pre><code class=\"language-python python\">def all_subsets(*args):\n  from collections import Iterable\n  from itertools import permutations as permute\n  if len(args) == 1:\n    if not isinstance(args[0], Iterable):\n      args = [args[0]]\n    else:\n      args = args[0]\n  \n  output = []\n  for i in permute(args):\n    output.append(i)\n  \n  return output<\/code><\/pre><\/noscript>\n<p>There&#8217;s probably reasons why it&#8217;s ugly, and certainly ways to do it better. What I like about this though is that it handles pretty much anything you throw at it, aside from a single non-iterable object I suppose! So calling &#8220;all_subsets(1,2,3,4)&#8221;, or &#8220;all_subsets(&#8216;funny&#8217;)&#8221;, or &#8220;all_subsets([1,2,3,4])&#8221; or &#8220;all_subsets({&#8216;a&#8217;:1,&#8217;b&#8217;:2})&#8221;, or even all_subsets(1) all work and spit out a list of tuples of the permutations.<\/p>\n<p>A possible extension would be to convert back into the form originally provided &#8211; but I think that a standard form of return may be more useful. Regardless, this is a neat tool that I will keep in my box.<\/p>\n<p>Edit: I made a modification to the above, so that it can work with any iterable or non-iterable object:<\/p>\n<script src=\"https:\/\/gist.github.com\/1166285.js\"><\/script><noscript><pre><code class=\"language-python python\">def all_subsets(*args):\n  from collections import Iterable\n  from itertools import permutations as permute\n  if len(args) == 1:\n    if not isinstance(args[0], Iterable):\n      args = [args[0]]\n    else:\n      args = args[0]\n  \n  output = []\n  for i in permute(args):\n    output.append(i)\n  \n  return output<\/code><\/pre><\/noscript>\n","protected":false},"excerpt":{"rendered":"<p>Disclaimer: this post has some lousy code and a serious factual error. Throughout, I am speaking about a method of generating all permutations of a set, while saying that I&#8217;m speaking about generating all subsets of a set! I have written a newer post which integrates content from a comment by Owen Jacobson, along with [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[47,51,48,49],"_links":{"self":[{"href":"https:\/\/wcarss.ca\/log\/wp-json\/wp\/v2\/posts\/280"}],"collection":[{"href":"https:\/\/wcarss.ca\/log\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wcarss.ca\/log\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wcarss.ca\/log\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wcarss.ca\/log\/wp-json\/wp\/v2\/comments?post=280"}],"version-history":[{"count":10,"href":"https:\/\/wcarss.ca\/log\/wp-json\/wp\/v2\/posts\/280\/revisions"}],"predecessor-version":[{"id":308,"href":"https:\/\/wcarss.ca\/log\/wp-json\/wp\/v2\/posts\/280\/revisions\/308"}],"wp:attachment":[{"href":"https:\/\/wcarss.ca\/log\/wp-json\/wp\/v2\/media?parent=280"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wcarss.ca\/log\/wp-json\/wp\/v2\/categories?post=280"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wcarss.ca\/log\/wp-json\/wp\/v2\/tags?post=280"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}