       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:= Timing[sss = allSubsets[Array[a,9]];]
Out= {0.02 Second, Null}

In:= Length[sss]
Out= 512

Harder test:

In:= Timing[sss = allSubsets[Array[a,20]];]
Out= {28.52 Second, Null}

In:= Length[sss]
Out= 1048576

You can obtain a result sorted by length using, say,

ss2 = Sort[sss, Length[#1]<=Length[#2]&];

suspect it is similar to that given above.

In:= <<DiscreteMath`Combinatorica`

In:= ?Subsets
Subsets[l] gives all subsets of set l.

In:= Timing[sss = allSubsets[Array[a,15]];]
Out= {0.84 Second, Null}

In:= Timing[ttt=Subsets[Array[a,15]];]
Out= {1.02 Second, Null}

In:= Sort[sss]===Sort[ttt]
Out= 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:= Timing[sss = allSubsets2[Array[a,15]];]
Out= {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