Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2011

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

Search the Archive

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




  • Prev by Date: Re: get rid of I in the result of an integral
  • Next by Date: Re: get rid of I in the result of an integral
  • Previous by thread: Re: k-permutations enumeration
  • Next by thread: Re: k-permutations enumeration