Re: generating submultisets with repeated elements
- To: mathgroup at smc.vnet.net
- Subject: [mg103960] Re: generating submultisets with repeated elements
- From: "Kurt TeKolste" <tekolste at fastmail.us>
- Date: Tue, 13 Oct 2009 23:22:11 -0400 (EDT)
- References: <ha4r9k$d0h$1@smc.vnet.net>
Bob
I've lost track of all of the solutions in this thread, so this may be a
repeat.
The proof that the number of k-set with repetition with elements from
1...n yields a functional expression that seems to be one of the most
efficient thus far offered and has the advantage of simplicity.
>>>>>>>>>>The idea of the proof<<<<<<<<<<<<
For any k-subset of {1,..,n+k-1} (i.e. without repetitions) list the
elements in ascending order. Since the order is ascending, the ith
member of the list must be no less than i. If you subtract 0 from the
first element of the list, 1 from the second, ..., i-1 from the ith, ..,
k-1 from the last you will have a list selected from 1..n with
repetitions.
>>>>>>>>>>Code based on the proof<<<<<<<<<<<<<<
Note: this depends upon Subsets returning values in increasing order
coinSetIndices[n_, k_] := Function[i, (# - Range[0, i - 1]) & /@
Subsets[Range[n + i - 1], {i}]] /@ Range[k]
>>>Quick check (Need to flatten into one list)<<<
In[62]:= Flatten[coinSetIndices[3, 2], 1]
Out[62]= {{1}, {2}, {3}, {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3,
3}}
>>>Timing test: eight sets, one for each i<<<
In[3]:= Length /@ coinSetIndices[20, 8] // Timing
Out[3]= {4.274, {20, 210, 1540, 8855, 42504, 177100, 657800, 2220075}}
>>>>Timing test: flatten into one list (Seems that removing the inner structure is pretty expensive).<<<
In[2]:= Length[Flatten[coinSetIndices[20, 8], 1]] // Timing
Out[2]= {5.866, 3108104}
ekt
Regards,
Kurt Tekolste