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