MathGroup Archive 2005

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: How to print on paper big matrixes ?
  • Next by Date: Re: Avoiding divide by zero error in NDSolve
  • Previous by thread: Re: permutations
  • Next by thread: Mathematica, Linux and OpenMosix