       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:= Flatten[coinSetIndices[3, 2], 1]

Out= {{1}, {2}, {3}, {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3,
3}}

>>>Timing test: eight sets, one for each i<<<

In:= Length /@ coinSetIndices[20, 8] // Timing

Out= {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:= Length[Flatten[coinSetIndices[20, 8], 1]] // Timing

Out= {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