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