Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Combinatorical efficiency

• To: mathgroup at smc.vnet.net
• Subject: [mg40476] Re: Combinatorical efficiency
• From: atelesforos at hotmail.com (Orestis Vantzos)
• Date: Mon, 7 Apr 2003 04:55:25 -0400 (EDT)
• References: <b6lvqe$eel$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

If you think about it, since order is not an issue, the only thing you
need to know is how many times each element is drawn. Hence you need
to find all the ways a sum of na drawings can be separated into nr
distinct no of drawings.
The function that does this is Combinatorica`Compositions:

orestisComb[na_,nr_] := (Flatten[MapIndexed[Table[#2, {#1}] &, #]] &
/@
        Compositions[na, nr + 1]) - 1

Orestis

"Gareth J. Russell" <gjr2008 at columbia.edu> wrote in message news:<b6lvqe$eel$1 at smc.vnet.net>...
> 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

• Follow-Ups:
  • Re: Re: Combinatorical efficiency
    • From: Dr Bob <majort@cox-internet.com>