Re: Re: Combinatorical efficiency
- To: mathgroup at smc.vnet.net
- Subject: [mg40471] Re: [mg40457] Re: [mg40433] Combinatorical efficiency
- From: Rob Pratt <rpratt at email.unc.edu>
- Date: Mon, 7 Apr 2003 04:54:07 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
On Sun, 6 Apr 2003, Rob Pratt wrote:
> On Sat, 5 Apr 2003, Gareth J. Russell wrote:
>
> > Hi,
> >
> > I am looking for an efficient (read fast) way to generate the set of all
> > combinations of na elements drawn with replacement from a set of nr
> > distinct elements. The number of these, of course is
> >
> > In[53]:=
> > numcombs[na_,nr_]:=((nr+1)+na-1)!/(na!*((nr+1)-1)!)
> >
> > In[106]:=
> > numcombs[3,4]
> >
> > Out[106]=
> > 35
> >
> > Just for illustration, here's a super-inefficient example that generates
> > all subsets of the right size, then pares them down to just the unique
> > combinations. I'm assuming that the set of elements is {0,1,2,...,nr-1},
> > and using the KSubsets function from the Combinatorica package.
> >
> > In[111]:=
> > tcombs[na_,nr_]:=KSubsets[Flatten[Table[Range[0,nr],{na}]],na]
> >
> > In[112]:=
> > temp1=tcombs[3,4];
> > temp2=Union[Map[Sort[#]&,temp1]]
> > Length[temp2]
> >
> > Out[113]=
> > {{0,0,0},{0,0,1},{0,0,2},{0,0,3},{0,0,4},{0,1,1},{0,1,2},{0,1,3},{
> > 0,1,4},{0,2,2},{0,2,3},{0,2,4},{0,3,3},{0,3,4},{0,4,4},{1,1,1},{
> > 1,1,2},{1,1,3},{1,1,4},{1,2,2},{1,2,3},{1,2,4},{1,3,3},{1,3,4},{
> > 1,4,4},{2,2,2},{2,2,3},{2,2,4},{2,3,3},{2,3,4},{2,4,4},{3,3,3},{
> > 3,3,4},{3,4,4},{4,4,4}}
> >
> > Out[114]=
> > 35
> >
> > This gets highly unwieldy as na and nr increase. Any suggestions?
> >
> > Thanks in advance,
> >
> > Gareth Russell
> > Columbia University
>
>
> You seem to have confused nr and nr + 1.
And I seem to have confused na and nr.
> The correct formula should be
> numcombs[na_,nr_]:=(nr+na-1)!/(na!*(nr-1)!)
Correct.
> which is just Binomial[nr + na - 1, nr].
Incorrect. It's Binomial[nr + na - 1, na].
> (Among nr + na - 1 slots for nr dots and na - 1 dividers, choose where
> the nr dots go.) For your example, take na = 3 and nr = 5 (your five
> distinct elements are {0, 1, 2, 3, 4}), yielding Binomial[7, 3] = 35.
Let me instead call the parameters n and k. We want to choose k elements,
with repetition, from among n elements. The resulting unordered k-tuples
are called multisets, and the number of k-multisets of an n-set is
sometimes called "n multichoose k" to generalize the phrase "n choose k"
used for k-subsets of an n-set. To count the k-multisets of an n-set,
imagine a row of k dots and n - 1 dividers. The number of dots preceding
the first divider is the number of 1's in the multiset. For i = 2 to n - 1,
the number of dots between dividers i - 1 and i is the number of i's in
the k-multiset. The number of dots after the last divider is the number
of n's in the multiset. For example, with n = 5 and k = 7,
. . | . | . . . | | . represents {1, 1, 2, 3, 3, 3, 5}.
This correspondence gives a bijection between k-multisets of an n-set and
permutations of k dots and n - 1 dividers. There are
(k + n - 1)! / (k! (n - 1)!) = Binomial[n + k - 1, k]
such permutations. Now take k = na and n = nr. The code below is still
correct for na = 3 and nr = 5, where your base set is {0, 1, 2, 3, 4}.
> Here's a more efficient way of getting the 35 triples:
>
> Flatten[Table[{x1,x2,x3},{x1,0,4},{x2,x1,4},{x3,x2,4}],2]
Rob Pratt
Department of Operations Research
The University of North Carolina at Chapel Hill
rpratt at email.unc.edu
http://www.unc.edu/~rpratt/