Counting And Listing All Permutations

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 than 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.

---

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

---

What if applet does not run?

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(i-1, j-1);    // swap values at positions (i-1) and (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)

Permutations

• Various ways to define a permutation
• Counting and listing all permutations
• Johnson-Trotter Algorithm: Listing All Permutations

Transpositions

• The Futurama Theorem and Puzzle
• A Shuttle Puzzle

Groups of Permutations

• Group multiplication of permutations
• Permutations as a Product of Transpositions
• Product of permutations
• Recombining Permutations

Sliders

• Sam Loyd's Fifteen
• Lucky 7
• Happy 8
• Blithe 12
• Slider puzzles

Puzzles on graphs

Equation in Permutations

|Contact| |Front page| |Contents| |Algebra| |Up|

Copyright © 1996-2018 Alexander Bogomolny