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