Re: permutations

*To*: mathgroup at smc.vnet.net*Subject*: [mg62458] Re: permutations*From*: Peter Pein <petsie at dordos.net>*Date*: Fri, 25 Nov 2005 02:24:56 -0500 (EST)*References*: <dm1jov$n4c$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Francisco Gutierrez schrieb: > Dear Group: > If I do for example: > Permutations[{x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12}], > my computer runs out of memory. > This is not such a poor computer. Actually, I would need to do > permutations of lists of Length 20, perhaps 25. I am aware > these calculations are big (Length[x]!), but I wonder if there > is some way around the problem. Compilating Permutations? > But then how? Can somebody help me? > Francisco Gutiérrez > > > Hi Francisco, I don't know whether it is easy to apply in your task to generate one permutation after the other. There is NextPermutation[] in DiscreteMath`Combinatorica`, but you can do faster: nextPermutation[p_List] := Block[{p1, p2, i, r}, p1 = p[[i = Last[Pick[Range[Length[p] - 1], Positive[Rest[p] - Most[p]]]]]]; r = Drop[p, i]; Join[Take[p, i - 1], {p2 = Min[Pick[r, Positive[r - p1]]]}, Sort[r /. p2 -> p1]]] <<DiscreteMath`Combinatorica` Timing[p = Range[9]; Do[p = NextPermutation[p], {9!/2}]; p] {12.25*Second, {5, 4, 9, 8, 7, 6, 3, 2, 1}} Timing[p = Range[9]; Do[p = nextPermutation[p], {9!/2}]; p] {8.141*Second, {5, 4, 9, 8, 7, 6, 3, 2, 1}} Even at this speed you would need 8.141*20!/(9!/2)/3600/24/365 = 3.46*10^6 years to generate all Permutations of Range[20], which is some 4 million years less than Deep Thought took to calculate 42 ;-) Peter