       Re: k-permutations enumeration

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

```If I Quit between testing these methods, the generating function approach
no longer wins:

Brute force:

Quit

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.008319, 187957770}

Less brute:

Quit

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

{0.004302, 187957770}

With generating functions:

Quit

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[{4, 5, 8, 3}, 15] // Timing

{0.034327, 187957770}

On a second try, the last method is ridiculously fast:

fx[{4, 5, 8, 3}, 15] // Timing

{0.000792, 187957770}

Bobby

On Wed, 16 Feb 2011 14:18:33 -0600, DrMajorBob <btreat1 at austin.rr.com>
wrote:

> I looked here and there, but didn't find a closed form or a built-in
> function.
>
> Here's a brute force method (probably a repeat of someone else's),
> followed by a minor simplification (I think) of a Dana DeLouis solution.
>
> (I needed to work it out both ways for my own benefit, and brute force
> was surprisingly fast, I thought.)
>
> 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}
>
> or
>
> 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[{4, 5, 8, 3}, 15] // Timing
>
> {0.000743, 187957770}
>
> Bobby
>
> On Wed, 16 Feb 2011 03:32:26 -0600, Daniel Lichtblau <danl at wolfram.com>
> wrote:
>
>> Michal Kvasnicka wrote:
>>> Once again... is there any enumeration (closed form) formula? The
>>> problem looks like simple combinatorics problem, but I can not find
>>> any relevant formula.
>>>
>>> The above mentioned algorithms looks very good, but I am still looking
>>> for closed form formula.
>>>
>>> Michal
>>>
>>
>> I do not believe there is a closed form in the sense you are seeking.
>> The method/algorithm that looks like
>> Coefficient[Product[Sum[...]],...]
>> is, in some sense, a closed form. That is to say, there is a notation in
>> the literature for exactly this computation. But like any special
>> function, that does not imply the numeric computation will be trivial.
>>
>> Daniel Lichtblau
>> Wolfram Research
>>
>>
>
>

--
DrMajorBob at yahoo.com

```

• Prev by Date: Re: NInegrate Bug
• Next by Date: Re: k-permutations enumeration
• Previous by thread: Re: k-permutations enumeration
• Next by thread: Re: k-permutations enumeration