Re: Re: Re: generating submultisets with repeated

*To*: mathgroup at smc.vnet.net*Subject*: [mg103741] Re: [mg103700] Re: [mg103681] Re: generating submultisets with repeated*From*: "Kurt TeKolste" <tekolste at fastmail.us>*Date*: Sun, 4 Oct 2009 05:37:17 -0400 (EDT)*References*: <DE9DE45304B6FA4EBE8252CD4EBDA2418286B95F41@PBI-NAMSG-02.MGDPBI.global.pvt>

A simpler trick is to simply repeat all of the elements of the set a sufficient number of times. In[100]:= coinSets[set_List, size_Integer] := Union[Subsets[Flatten[ConstantArray[#, size] & /@ set], {1, size}]] In[101]:= coinSets[{1, 3, 4}, 3] Out[101]= {{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}} In[102]:= coinSets[{1, 3, 4, 9}, 3] Out[102]= {{1}, {3}, {4}, {9}, {1, 1}, {1, 3}, {1, 4}, {1, 9}, {3, 3}, {3, 4}, {3, 9}, {4, 4}, {4, 9}, {9, 9}, {1, 1, 1}, {1, 1, 3}, {1, 1, 4}, {1, 1, 9}, {1, 3, 3}, {1, 3, 4}, {1, 3, 9}, {1, 4, 4}, {1, 4, 9}, {1, 9, 9}, {3, 3, 3}, {3, 3, 4}, {3, 3, 9}, {3, 4, 4}, {3, 4, 9}, {3, 9, 9}, {4, 4, 4}, {4, 4, 9}, {4, 9, 9}, {9, 9, 9}} In[103]:= coinSets[{a, b, c}, 3] Out[103]= {{a}, {b}, {c}, {a, a}, {a, b}, {a, c}, {b, b}, {b, c}, {c, c}, {a, a, a}, {a, a, b}, {a, a, c}, {a, b, b}, {a, b, c}, {a, c, c}, {b, b, b}, {b, b, c}, {b, c, c}, {c, c, c}} ekt On Sat, 03 Oct 2009 09:01 -0400, "David Bevan" <david.bevan at pb.com> wrote: > Daniel, > > Your 'solution' is incorrect since multisets are repeated (e.g. {1,3} and > {3,1} are both produced). In fact it simply demonstrates the problem. The > output I want for your example data is: > > {{1},{3},{4},{9},{1,1},{1,3},{1,4},{1,9},{3,3},{3,4},{3,9},{4,4},{4,9},{9,9},{1,1,1},{1,1,3},{1,1,4},{1,1,9},{1,3,3},{1,3,4},{1,3,9},{1,4,4},{1,4,9},{1,9,9},{3,3,3},{3,3,4},{3,3,9},{3,4,4},{3,4,9},{3,9,9},{4,4,4},{4,4,9},{4,9,9},{9,9,9}} > > Btw, who is responsible for the Combinatorica package? Is there some way > of requesting or perhaps more usefully helping to provide new functions? > Certainly a (more general) SubMultiset function would perhaps be of use > to others. > > Thanks. > > David %^> > ________________________________________ > From: Daniel Lichtblau [danl at wolfram.com] > Sent: 02 October 2009 16:07 > To: David Bevan > Subject: [mg103700] Re: [mg103681] Re: generating submultisets with > repeated elements > > David Bevan wrote: > > 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 %^> > > Outer can be put to good use here. > > sublists[k_,lst_] := > Flatten[Outer[List,Apply[Sequence,Table[lst,{k}]]], k-1] > > coinSets2[k_,lst_] := Apply[Join, Table[sublists[j,lst], {j,k}]] > > In[23]:= ll = {1,3,4,9}; > > In[24]:= InputForm[coinSets2[3,ll]] > > Out[24]//InputForm= > {{1}, {3}, {4}, {9}, {1, 1}, {1, 3}, {1, 4}, {1, 9}, {3, 1}, {3, 3}, {3, > 4}, > {3, 9}, {4, 1}, {4, 3}, {4, 4}, {4, 9}, {9, 1}, {9, 3}, {9, 4}, {9, 9}, > {1, 1, 1}, {1, 1, 3}, {1, 1, 4}, {1, 1, 9}, {1, 3, 1}, {1, 3, 3}, {1, > 3, 4}, > {1, 3, 9}, {1, 4, 1}, {1, 4, 3}, {1, 4, 4}, {1, 4, 9}, {1, 9, 1}, {1, > 9, 3}, > {1, 9, 4}, {1, 9, 9}, {3, 1, 1}, {3, 1, 3}, {3, 1, 4}, {3, 1, 9}, {3, > 3, 1}, > {3, 3, 3}, {3, 3, 4}, {3, 3, 9}, {3, 4, 1}, {3, 4, 3}, {3, 4, 4}, {3, > 4, 9}, > {3, 9, 1}, {3, 9, 3}, {3, 9, 4}, {3, 9, 9}, {4, 1, 1}, {4, 1, 3}, {4, > 1, 4}, > {4, 1, 9}, {4, 3, 1}, {4, 3, 3}, {4, 3, 4}, {4, 3, 9}, {4, 4, 1}, {4, > 4, 3}, > {4, 4, 4}, {4, 4, 9}, {4, 9, 1}, {4, 9, 3}, {4, 9, 4}, {4, 9, 9}, {9, > 1, 1}, > {9, 1, 3}, {9, 1, 4}, {9, 1, 9}, {9, 3, 1}, {9, 3, 3}, {9, 3, 4}, {9, > 3, 9}, > {9, 4, 1}, {9, 4, 3}, {9, 4, 4}, {9, 4, 9}, {9, 9, 1}, {9, 9, 3}, {9, > 9, 4}, > {9, 9, 9}} > > Daniel Lichtblau > Wolfram Research > Regards, Kurt Tekolste