Counting And Listing All Permutations

The applet below displays all the permutations of the set Nn = {1, ..., n}, where n changes from 0 to 7. N0 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 N7 to get listed on my 100 MHz machine. (In the development environment, N8 is permuted faster than N7 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 S3. Observing permutations as products of cycles it becomes obvious that elements of S3 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, 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
          for (int i = 0; i < N; i++)
            if (Value[i] == 0)
        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);
  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) 
      else {
        for (int i = 0; i < n; i++) 
          if (n % 2 == 1)  // if n is odd
            swap(0, n-1);
          else            // if n is even
            swap(i, n-1);


  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)


  • Transpositions
  • Groups of Permutations
  • Sliders
  • Puzzles on graphs
  • Equation in Permutations

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

    Copyright © 1996-2018 Alexander Bogomolny

  • 71611897