Re: k-permutations enumeration

• To: mathgroup at smc.vnet.net
• Subject: [mg116553] Re: k-permutations enumeration
• From: DrMajorBob <btreat1 at austin.rr.com>
• Date: Sat, 19 Feb 2011 05:14:34 -0500 (EST)

```Compositions scaled badly at this machine:

Needs["Combinatorica`"];

v = {4, 5, 8, 3, 7, 2, 5};
n = 25;
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[v, n] // Timing

{9.44586, 38474604708335195400}

v = {4, 5, 8, 3, 7, 2, 5};
n = 25;
fx[v_, n_] := Module[{t}, t = Normal@Series[E^x, {x, 0, Max@v}];
t = Times @@ (Take[t, 1 + #] & /@ v);
n! Coefficient[t, x, n]]
fx[v, n] // Timing

{0.009512, 38474604708335195400}

v = {4, 5, 8, 3, 7, 2, 5};
k = Length@v;
n = 25;
Timing@Module[{v2 = Reverse@Sort@v, vk, f1, s, f2, p},
vk[k_] := vk[k] = Take[v2, k];
f1 = (j = Length@#; And @@ Thread[# <= vk@j]) &;
s = Select[IntegerPartitions[n, k], f1];
f2 = And @@ Thread[# <= v] &;
p = n! Length@
Select[Permutations@PadRight[#, k], f2]/(Times @@
Factorial@#) &;
Total[p /@ s]
]

{1.84519, 38474604708335195400}

Bobby

On Fri, 18 Feb 2011 03:36:51 -0600, Dana DeLouis <dana.del at gmail.com>
wrote:

> 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.
>
> 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]];
> 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
>
>
>

--
DrMajorBob at yahoo.com

```

• Prev by Date: Re: NInegrate Bug
• Next by Date: Re: problem with NDSolve::dvnoarg:
• Previous by thread: Re: k-permutations enumeration
• Next by thread: MathKernel -script in MacOSX