Re: k-permutations enumeration
- To: mathgroup at smc.vnet.net
- Subject: [mg116533] Re: k-permutations enumeration
- From: Dana DeLouis <dana.del at gmail.com>
- Date: Fri, 18 Feb 2011 04:36:51 -0500 (EST)
On Feb 17, 5:19 am, DrMajorBob <btre... at austin.rr.com> wrote:
> If I Quit between testing these methods, the generating function approach
> no longer wins:
>
> Brute force:
>
> > Timing[v = {4, 5, 8, 3};
> > 15!/Times @@@
> > Factorial@
> > Select[Flatten[
> > Permutations /@
> > ReplaceRepeated[
> > IntegerPartitions[15, 4], {x__} /; Length@{x} < 4 :> {x, 0}],
> > 1], And @@ Thread[# <= v] &] // Total]
>
> > {0.007887, 187957770}
> --
> DrMajor... at yahoo.com
Hi. Just to share, here's an earlier attempt I had.
Needs["Combinatorica`=94];
fx1[v_List,n_Integer]:=Module[{c,t},
c=Compositions[n,Length[v]];
t=Inner[LessEqual,c,v,And] ;
Apply[Multinomial,Pick[c,t,True],1]//Tr]
fx1[{3,4,5,8},15]//Timing
{0.004957,187957770}
I couldn=92t figure this idea out, but I saw it in your code. Thanks.
... And@@Thread[#<=v]&
I thought that idea would be faster, but for some reason it appears to be a =93hair=94 slower.
I don=92t see why it would be slightly slower. Hmmm.
fx2[v_List,n_Integer]:=Module[{c,t},
c=Compositions[n,Length[v]];
t=Select[c,And@@Thread[#<=v]&];
Apply[Multinomial,t,1]//Tr]
fx2[{3,4,5,8},15]//Timing
{0.008464,187957770}
PS. Thanks for the reminder the n! should be factored out.
n! Coefficient[t, x, n]
= = = = = = = = = =
: >)
Dana DeLouis