Re: Combinatorical efficiency
- To: mathgroup at smc.vnet.net
- Subject: [mg40457] Re: [mg40433] Combinatorical efficiency
- From: Rob Pratt <rpratt at email.unc.edu>
- Date: Sun, 6 Apr 2003 04:34:36 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
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. The correct formula should be numcombs[na_,nr_]:=(nr+na-1)!/(na!*(nr-1)!) which is just Binomial[nr + na - 1, nr]. (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. 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/