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