Re: generating subsets

*To*: mathgroup at smc.vnet.net*Subject*: [mg21626] Re: [mg21588] generating subsets*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Tue, 18 Jan 2000 02:35:14 -0500 (EST)*References*: <200001160856.DAA10812@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Michael Gass wrote: > > I need an _efficient_ procedure for generating all the subsets > of a given set. The procedure should produce output as follows: > > subSets[{a,b,c}] > produces > {{}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}} > > I have written a recursive procedure to do this, but > it takes quite a while to generate, say, the 512 subsets > of a 9 element set and I need to work with somewhat larger > sets. > > Thanks > > -- > Michael Gass Department of Mathematics > phone: 320 363-3090 St. John's University > email: mgass at csbsju.edu Collegeville, MN 56321-3000 I think this has come up on mathgroup several times before but (for those of us who suffer mild web-impairments) it is quicker to write code for it than to search the archives. Below is one technique. I am fairly certain I have seen others that are as fast or faster but cannot recall the details. allSubsets[{a_}] := {{},{a}} allSubsets[a_List] := With[ {s1=allSubsets[Drop[a,-1]],ll=Last[a]}, Join[s1,Map[Append[#,ll]&,s1]] ] Test: In[10]:= Timing[sss = allSubsets[Array[a,9]];] Out[10]= {0.02 Second, Null} In[11]:= Length[sss] Out[11]= 512 Harder test: In[16]:= Timing[sss = allSubsets[Array[a,20]];] Out[16]= {28.52 Second, Null} In[17]:= Length[sss] Out[17]= 1048576 You can obtain a result sorted by length using, say, ss2 = Sort[sss, Length[#1]<=Length[#2]&]; There is already code subset-generating in a standard add-on package. I suspect it is similar to that given above. In[18]:= <<DiscreteMath`Combinatorica` In[20]:= ?Subsets Subsets[l] gives all subsets of set l. In[21]:= Timing[sss = allSubsets[Array[a,15]];] Out[21]= {0.84 Second, Null} In[22]:= Timing[ttt=Subsets[Array[a,15]];] Out[22]= {1.02 Second, Null} In[24]:= Sort[sss]===Sort[ttt] Out[24]= True The procedure allSubsets shown above is recursive. Below is a nonrecursive method that seems to scale about 10 times slower. allSubsets2[a_List] := With[ {vecs=Map[IntegerDigits[#,2,Length[a]]&, Range[0,2^Length[a]-1]]}, Map[Inner[Times,#,a,List]&, vecs] /. 0->Sequence[] ] In[59]:= Timing[sss = allSubsets2[Array[a,15]];] Out[59]= {10.2 Second, Null} Daniel Lichtblau Wolfram Research