Re: Re: generating submultisets with repeated elements
- To: mathgroup at smc.vnet.net
- Subject: [mg103742] Re: [mg103681] Re: generating submultisets with repeated elements
- From: Adriano Pascoletti <adriano.pascoletti at dimi.uniud.it>
- Date: Sun, 4 Oct 2009 05:37:28 -0400 (EDT)
- References: <DE9DE45304B6FA4EBE8252CD4EBDA2418286B95F41@PBI-NAMSG-02.MGDPBI.global.pvt>
David,my solution starts with a subset In[1]:= start = {1, 3, 4} Out[1]= {1, 3, 4} and generates the submultiset of size 1 In[3]:= submulti1 = ({#1} & ) /@ start Out[3]= {{1}, {3}, {4}} The following function generates submultisets of size n+1 from a given multisubset of size n grow[submultiset_] := (Join[submultiset, #1] & ) /@ Cases[start, x_ /; x >= Last[submultiset] :> {x}]; Nest grow k-1 times and Join the lists In[9]:= Join @@ NestList[Join @@ grow /@ #1 & , submulti1, 2] Out[9]= {{1}, {3}, {4}, {1, 1}, {1, 3}, {1, 4}, {3, 3}, {3, 4}, {4, 4}, {1, 1, 1}, {1, 1, 3}, {1, 1, 4}, {1, 3, 3}, {1, 3, 4}, {1, 4, 4}, {3, 3, 3}, {3, 3, 4}, {3, 4, 4}, {4, 4, 4}} coinSets[start_, k_] := Join @@ NestList[Join @@ grow /@ #1 & , ({#1} & ) /@ start, k - 1] In[8]:= coinSets[{1, 3, 4}, 3] Out[8]= {{1}, {3}, {4}, {1, 1}, {1, 3}, {1, 4}, {3, 3}, {3, 4}, {4, 4}, {1, 1, 1}, {1, 1, 3}, {1, 1, 4}, {1, 3, 3}, {1, 3, 4}, {1, 4, 4}, {3, 3, 3}, {3, 3, 4}, {3, 4, 4}, {4, 4, 4}} Adriano Pascoletti 2009/10/2 David Bevan <david.bevan at pb.com> > I've now tried the following, which avoids generating the extra multisets: > > > coinSets[s_,k_]:=Flatten[Table[subMultiSets[s,i],{i,k}],1] > > > > subMultiSets[s_,k_]:=smsLoop[{},s,k] > > > > smsLoop[{ts___},{x_},1]:={{ts,x}} > > > > smsLoop[t:{ts___},{x_,xs___},1]:=Prepend[smsLoop[t,{xs},1],{ts,x}] > > > > smsLoop[{ts___},s:{x_},k_]:=smsLoop[{ts,x},s,k-1] > > > > > smsLoop[t:{ts___},s:{x_,xs___},k_]:=Join[smsLoop[{ts,x},s,k-1],smsLoop[t,{xs},k]] > > > > Any suggestions for a better approach? > > > > David %^> > > > ________________________________ > From: David Bevan > Sent: 01 October 2009 18:57 > To: mathgroup at smc.vnet.net > Subject: [mg103681] generating submultisets with repeated elements > > I'm new to Mathematica, so if I've missed something obvious, my apologies. > > I want a function to generate a list of "submultisets" with up to k > elements of a set s, allowing elements from s to be repeated. > > The following works, but is very inefficient since each multiset is > generated multiple times and then sorted and then repeats deleted: > > > coinSets[s_,k_]:=DeleteDuplicates[Sort/@Flatten[Tuples[s,#]&/@Range[k],1]] > > > > coinSets[{1,3,4},3] > > > > > {{1},{3},{4},{1,1},{1,3},{1,4},{3,3},{3,4},{4,4},{1,1,1},{1,1,3},{1,1,4},{1,3,3},{1,3,4},{1,4,4},{3,3,3},{3,3,4},{3,4,4},{4,4,4}} > > > > I assumed there would be a suitable function in the Combinatorica package, > but I can't see anything -- which would be a bit odd for a combinatorial > package. What have I missed? > > > > Do I need to write my own (perhaps by looking at how KSubsets is > implemented) or is there some easy way of generating these multisets? > > > > Thanks. > > > > David %^> > > > > >