MathGroup Archive 2009

[Date Index] [Thread Index] [Author Index]

Search the Archive

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