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.
> ... 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
>
>
>
--
DrMajorBob at yahoo.com