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