Re: Re: generating submultisets with repeated elements
- To: mathgroup at smc.vnet.net
- Subject: [mg103700] Re: [mg103681] Re: generating submultisets with repeated elements
- From: David Bevan <david.bevan at pb.com>
- Date: Sat, 3 Oct 2009 09:01:09 -0400 (EDT)
- References: <DE9DE45304B6FA4EBE8252CD4EBDA2418286B95F41@PBI-NAMSG-02.MGDPBI.global.pvt>
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