MathGroup Archive 2003

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

Search the Archive

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


  • Prev by Date: Re: Import[ ] & ReadList[ ]; "Word" and "Record"
  • Next by Date: Re: Opinions about the "Oneliners"
  • Previous by thread: Re: functions
  • Next by thread: Re: Combinatorical efficiency