MathGroup Archive 2000

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: generating subsets

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                 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[


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[
	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

  • Prev by Date: Flat, OneIdentity Again
  • Next by Date: Re: Series expansion of ArcSin around 1
  • Previous by thread: Re: generating subsets
  • Next by thread: Series expansion of ArcSin around 1