Re: Re: Re: generating submultisets with
- To: mathgroup at smc.vnet.net
- Subject: [mg103735] Re: [mg103700] Re: [mg103681] Re: generating submultisets with
- From: danl at wolfram.com
- Date: Sun, 4 Oct 2009 05:36:11 -0400 (EDT)
> 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
Sorry, I had missed the detail of set vs. order list. Here is a method
that should do what you have in mind. For multisets of length k, the idea
is to use k iterators wherein each goes from the value of the previous one
up to the maximal value (the length of the input list).
multiSetsK[ll_, k_] := Module[
{x, n = Length[ll], itervars, iters},
itervars = Array[x, k + 1, 0];
x[0] = 1;
iters = Table[{x[i], x[i - 1], n}, {i, k}];
Flatten[
Table[Map[ll[[#]] &, Rest[itervars]], Evaluate[Sequence @@ iters]],
k - 1]
]
multiSetsUpToK[ll_, k_] := Join @@ Table[multiSetsK[ll, j], {j, k}]
ll = {1, 3, 4, 9};
In[92]:= multiSetsUpToK[ll, 3]
Out[92]= {{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}}
Daniel Lichtblau
Wolfram Research
______________________________
> 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\
>>[...]
>
> 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
>