MathGroup Archive 1997

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

Search the Archive

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


  • Prev by Date: Re: Frontend bug
  • Next by Date: Display is wrong
  • Previous by thread: NDSolve
  • Next by thread: Display is wrong