Combinatorical efficiency
- To: mathgroup at smc.vnet.net
- Subject: [mg40433] Combinatorical efficiency
- From: "Gareth J. Russell" <gjr2008 at columbia.edu>
- Date: Sat, 5 Apr 2003 03:59:44 -0500 (EST)
- Organization: Columbia University
- Sender: owner-wri-mathgroup at wolfram.com
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