Re: Re: Combinatorical efficiency
- To: mathgroup at smc.vnet.net
- Subject: [mg40497] Re: [mg40476] Re: Combinatorical efficiency
- From: Dr Bob <majort at cox-internet.com>
- Date: Tue, 8 Apr 2003 03:03:26 -0400 (EDT)
- References: <b6lvqe$eel$1@smc.vnet.net> <200304070855.EAA08007@smc.vnet.net>
- Reply-to: majort at cox-internet.com
- Sender: owner-wri-mathgroup at wolfram.com
That's drawing from nr + 1 elements (0 to nr), not from nr elements.
Isn't it?
Why not this, for easier understanding and more flexibility?
<< DiscreteMath`Combinatorica`
treatComb[nDraws_Integer, elements_List] := Sort@
(Flatten[MapIndexed[Table[elements[[#2]], {#1}] &, #]] & /@
Compositions[nDraws, Length@elements])
treatComb[nDraws_Integer, nElements_Integer] := treatComb[nDraws, Range[0,
nElements - 1]]
orestisComb[na_,nr_]:=(Flatten[MapIndexed[Table[#2,{#1}]&,#]]& /@
Compositions[na,nr+1])-1
treatComb[3, Range[0, 4]] == treatComb[3, 5] == Sort@orestisComb[3, 4]
True
Bobby
On Mon, 7 Apr 2003 04:55:25 -0400 (EDT), Orestis Vantzos
<atelesforos at hotmail.com> wrote:
> 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
>
>
--
majort at cox-internet.com
Bobby R. Treat
- References:
- Re: Combinatorical efficiency
- From: atelesforos@hotmail.com (Orestis Vantzos)
- Re: Combinatorical efficiency