The applet below displays all the permutations of the set N_n = {1,...,n}, where n changes from 0 to 7. N₀ is of course empty. There is no special reason for selecting 7 as the upper size of the allowed sets - the algorithms described below are quite general. The problem is that of speed. I did not have enough patience to wait for the 7! = 5040 permutations of N₇ to get listed on my 100 MHz machine. (In the development environment, N₈ is permuted faster then N₇ in a browser. P.S. This has been written in 1997!) Thus beware.

In the applet, every permutation is also presented as a product of cycles. For n = 3, we have a list of 6 elements of the symmetric group S₃. Observing permutations as products of cycles it becomes obvious that elements of S₃ represent rigid motions of an equilateral triangle. Indeed, envisage such a triangle and mark its vertices with numbers 1,2,3. Then (1 2 3) denotes the rotation of the vertices wherewith 1 goes to 2, 2 to 3, and 3 to 1. (1 3 2) is a rotation in the opposite direction. (1 2)(3) is the symmetry around the median from vertex 3, and so on.

The applet offers three algorithms that generate the list of all the permutations: Recursive, Lexicographic and an algorithm due to B. Heap. I'll describe each in turn. In all the algorithms, N denotes the number of items to be permuted.

1. Recursive algorithm

   The recursive algorithm is short and mysterious. It's executed with a call visit(0). Global variable level is initialized to -1 whereas every entry of the array Value is initialized to 0.

   void visit(int k)
   {
     level = level+1; Value[k] = level;    // = is assignment
   

     if (level == N)  // == is comparison
       AddItem();     // to the list box
     else
       for (int i = 0; i < N; i++)
         if (Value[i] == 0)
           visit(i);
   

     level = level-1; Value[k] = 0;
   }
   

   void AddItem()
{
  // Form a string from Value[0], Value[1], ... Value[N-1].
  // At this point, this array contains one complete permutation.
  // The string is added to the list box for display.
  // The function, as such, is inessential to the algorithms.
}


   Try this algorithm by hand to make sure you undestand how it works.

2. Lexicographic order and finding the next permutation

   Permutation f precedes a permutation g in the lexicographic (alphabetic) order iff for the minimum value of k such that f(k) g(k), we have f(k) < g(k). Starting with the identical permutation f(i) = i for all i, the second algorithm generates sequentially permutaions in the lexicographic order. The algorithm is described in [Dijkstra, p. 71].

   void getNext()
   {
     int i = N - 1;
   

     while (Value[i-1] >= Value[i]) i = i-1;
   

     int j = N;
   

     while (Value[j-1] <= Value[i-1]) j = j-1;
   

   // swap values at positions (i-1) and (j-1)
     swap(i-1, j-1);    
   

     i++; j = N;
   

     while (i < j)
  {
    swap(i-1, j-1);
    i++;
    j--;
  }
}


    

3. B. Heap's algorithm

   Heap's short and elegant algorithm is implemented as a recursive method HeapPermute [Levitin, p. 179]. It is invoked with HeapPermute(N).

   void HeapPermute(int n)
{
  if (n == 1)
    AddItem();
  else {
    for (int i = 0; i < n; i++)

      HeapPermute(n-1);

      if (n % 2 == 1) // if n is odd
        swap(0, n-1);
      else            // if n is even
        swap(i, n-1);
}


Reference

1. A. Levitin, Introduction to The Design & Analysis of Algorithms, Addison Wesley, 2003
2. E. W. Dijkstra, A Discipline of Programming, Prentice-Hall, 1997 [FACSIMILE] (Paperback)
3. R. Sedgewick, Algorithms in C, Addison-Wesley, 3rd edition (August 31, 2001)

• Graphs
• Puzzles on graphs
  • Three Glass Puzzle (example)
  • Three Glass Puzzle in Barycentric Coordinates (example)
  • Sierpinski Gasket and Tower of Hanoi (example)
  • Sam Loyd's Fifteen
  • Sliders
  • Lucky 7
  • Happy 8
  • Blithe 12
  • Slider puzzles
• Permutations
  • Various ways to define a permutation
  • Counting and listing all permutations
  • Counting and listing all permutations: Johnson-Trotter
• Transpositions
  • A Shuttle Puzzle
• Groups of Permutations
  • Permutations as a Product of Transpositions
  • Group multiplication of permutations
  • Product of permutations
  • Recombining Permutations

Copyright © 1996-2009 Alexander Bogomolny