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/