Re: Lists and subsets
- To: mathgroup at smc.vnet.net
- Subject: [mg9529] Re: Lists and subsets
- From: Hein Hundal <junkmail at vicon.net>
- Date: Thu, 13 Nov 1997 01:39:58 -0500
- Sender: owner-wri-mathgroup at wolfram.com
In article <63rtgu$llg at smc.vnet.net>,
Daniel Lichtblau <danl at wolfram.com> wrote:
>
> Joana Nunes de Almeida wrote:
> >
> > Hello,
> >
> > I'm doing a project for my Programming course, but I'm having some
> > trouble whith one of the exercises.
> > I must define a function where when we put in a list the function gives
> > back the different parts of the list.
> >
> > exp: parts[{1,2}]
> > gives: [{1,2},{1},{2},{}]
> >
> > NB: I must define the function recursivly
> [snip]
>
> The question called for a recursive algorithm. Actually, it is quite a
> challenge (for me) to provide one that is not recursive. One way to do
> this is by making a Sequence of iterators, forming all possible {0,1}
> strings of length k, then using these to form subsets. It took me some
> fiddling with Flatten and other primitives before I got this working,
> and I am certain it can be done better, but here goes:
>
> subsets3[{}]={{}};
> subsets3[x_List] /; Length[x]>0 :=
> Module[{k,indx,indices,n=Length[x],l1},
> indx = Array[k,n];
> indices = Apply[Sequence, Map[{#,0,1}&, indx]];
> l1 = Partition[Flatten[Table[k[j], Evaluate[indices], {j,1,n}]],
> n]= ;
> Map[Flatten, Table[If [l1[[m,j]]==1, x[[j]], {}],
> {m,1,2^n},{j,1,n}]]
> ]
> subsets3[{a,b,c,d}]
> [snip]
>
Another non-recursive algorithm:
joinlist[listofsubsets_List, element_] :=
Join[ listofsubsets, Append[#, element]& /@ listofsubsets];
subsets[set_List] := Fold[joinlist, {{}}, set];
This one executes about as fast or faster than the recursive version.
Hein Hundal
hundal at vicon.net