Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2000
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2000

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

Search the Archive

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


  • 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