[Date Index]
[Thread Index]
[Author Index]
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
Prev by Date:
**Re: Convert Graphics3D to Graphics2D. Is it possible?**
Next by Date:
**Re: Re: The graph of (x + 2)^(1/5) + 4 not plotted correctly**
Previous by thread:
**Re: generating submultisets with repeated elements**
Next by thread:
**Re: generating submultisets with repeated elements**
| |