Permutations - notes and programs

Notes:

Here is a tree, one way to look at a permutation of 4 things - in this case just the numbers {0, 1, 2, 3}.
We can also think of this as the permutations of array indices, in which case this looks like all the permutations of 4 items.

We can list these permutations as a table, reading from left to right

Among other things, you will note that finding a particular permutation on this list is very similar to looking up a word in a dictionary.
In other words, this presentation of the permutations is in dictionary order - sorted by the left most element, then the second element, and so on.

We should note that for n elements, there are n! permutations (n! is read n factorial - there are many references on line if you are not familiar with this concept).
n! gets to be large very quickly.

A parenthesized representation of this tree:
(. (0 (1 (2 3) (3 2)) (2 (1 3) (3 1)) (3 (1 2) (2 1))) (1 (0 (2 3) (3 2)) (2 (0 3) (3 0)) (3 (0 2) (2 0))) (2 (0 (1 3) (3 1)) (1 (0 3) (3 0)) (3 (0 1) (1 0))) (3 (0 (1 2) (2 1)) (1 (0 2) (2 0)) (2 (0 1) (1 0))))

Challenges

• List all the permutations of n objects - in our case, just the array indices {0, 1, 2, ..., n-1}
• Given a particular permutation of a set of indices, list the next one, or next few.

An example - how do we get the next permutation for the following one? Starting with a spoiler comment, and I have purposely chosen an interesting case:

current: 3 1 2 6 8 7 5 4 0
   next: 3 1 2 7 0 4 5 6 8

So, perhaps first comment is how did we decide what to do next? Well, here goes, with highlighting:

current: 3 1 2 6 8 7 5 4 0
   next: 3 1 2 7 0 4 5 6 8

The yellow is the longest ending string that is in reverse order (a[i] > a[i+1]).
The orange element is the target - again, think dictionary order.
Now comes the interesting part: of the elements in the yellow list, 7 is first element reading from the right that is larger than the target (6).
Thus - we exchange the 6 and 7 - which leaves the yellow list in decreasing order:

 current: 3 1 2 6 8 7 5 4 0
exchange: 3 1 2 7 8 6 5 4 0
 reverse: 3 1 2 7 0 4 5 6 8
    next: 3 1 2 7 0 4 5 6 8

And then we reverse the elements in the yellow list, giving us the cyan list.

List Them All - recursive solution

• We could just use the "get the next one" algorithm over and over again, but there is also a clever recursive algorithm that will solve this problem rather compactly.
• One problem with the recursive algorithm is that it is not good at solving the "get the next permutation" problem.
• Thinking about the tree at the top of this page, you will see the listing all the permutations is the same as listing all the paths in the tree, so we could use the same algorithm we use to list all the permutations as the one we would use to list all the paths in a tree!
• So we can already see that the problem of list all paths is the same as list all permutations.
• Return from algorithm?
• If we think of a permutation as an array of n integers, {0, 1, ..., n-1}, the return from the algorithm should be an array (n!) of these arrays.
• Thus, the return should be of type int [][], or to be even more precise, the following:
  int [n!][n]
• So, let's characterize the algorithm at a node of the tree above, say the top level node with value 1:
• this node has 3 children, all the elements of the array other than 1
• going one level deeper, say node 3 {1, 3}, we see the two children are 0 and 2.
  
• The insight here is that the children of a node are all the elements that are not in the path to that node and the node itself.
• For example, if n=9, and the path to the node we are considering is {4, 2, 8, 1}, the children of this node are going to be all the other elements {0, 3, 5, 6, 7}
• In this example, the path so far would be 4 → 2 → 8 → 1, and our algorithm should be listing all the child paths below this node.
• The inputs to the recursive part is the path so far (including this node), and the list of children of this node, and the return is going to be appending this node and the paths of all the children:
   
  paths // global variable
  list (children, path)
    if (children == null) return paths.add (path)
    for (each child c in children)
      list (children.remove(c), path.add(c))
  
• There are annoying technical issues in Java, and perhaps most languages, implementing the recursive call:
• making a good remove and add cycle work on the children data structure
• getting a new data structure for a path so far
  
• So here is some Java code that implements this algorithm, using Integer's as the base type, starting with the {0, 1, ..., n-1} array:
• In this code:
• there is one instance variable for the class: paths
• the recursive method is walk
• the method is void, with two parameters
• the base case is a leaf in the permutation tree
• walking starts at the top node with a list of the children
  
• a new path is instantiated a parent node (path)
  
• representing the path to the current parent node
  
• with the parent node added to that path
  
• that path is passed as a parameter to the child nodes
• also passed to the child nodes is the deleted list of indices (children)
  
• these are the nodes yet to be visited in the permutations under this parent node
  
• and a path is added to the list paths at a leaf node

(start code)

// File: Walking.java
// Date: Nov 19, 2017
// Author: Nicholas Duchon.
// Purpose: walking a tree recusively

import java.util.Scanner;
import java.util.ArrayList;

public class Walking {
   static Scanner stin = new Scanner (System.in);
  
   ArrayList <ArrayList <Integer>> paths = new ArrayList <> ();

   Walking () {
      System.out.print ("Number of elements: ");
      int n = stin.nextInt ();
      ArrayList <Integer> path = new ArrayList <> ();
      for (int i = 0; i < n; i++) {
         path.add(i);
      } // end for each element

      walk (path, new ArrayList <Integer> ());
     
      System.out.println (this.toString());

   } // end constructor
  
   void walk (ArrayList <Integer> children, ArrayList <Integer> path) {
      // base case - we have reached a leaf node, a path
      if (children.size() == 0) {
         paths.add (path);
         return;
      } // end if leaf

      for (int i = 0; i < children.size(); i++) {
         // get the i-th child
         int target = children.remove (i);
        
         // A new path for each child
         // Add that child to the new path so far
         ArrayList <Integer> newPath = new ArrayList <> ();
         newPath.addAll (path);
         newPath.add (target);

         walk (children, newPath);
        
         // return the i-th child to its previous position
         children.add (i, target);
      } // end for each child

   } // end method walk
  
   public String toString () {
      String st = "";
      st += "-- Number of permutations: " + paths.size();

      for (ArrayList <Integer> p: paths) {
         st += "\n";
         for (Integer i: p)
            st += " " + i;
      } //end for each path
      return st;
   } // end method toString
  
   public static void main (String args []) {
      Walking w = new Walking ();
   } // end main
} // end class Walking

(end code)

Get the Next One

For this, I have included a few static helper methods based on an array of integers, int [] q, which represents a permutation of the n indices: {0, 1, ..., n-1}.

• Printing times permutations, starting with q, showCount will show a count at the start of each line, and showParan will show the cycle format of that permuation
        String st = "Initialized array of size: " + q.length + "\n";
        checkPermutation (q);
        for (i = 1; i <= times; i++) {
           st += "\n";
           if (showCount) st += String.format ("%5d - ", i);
           st += toString(q);
           if (showParan)
              st += " = " + toParanString(q);
           q = nextPermutation(q);
        } // end for as many times as requested
    
        System.out.println (st);
• Sample output:
  Initialized array of size: 5
  
      1 - 1 2 3 4 0 =  (0 4 3 2 1)
      2 - 1 2 4 0 3 =  (0 3 4 2 1)
      3 - 1 2 4 3 0 =  (0 4 2 1) (3)
• checkPermutation - make sure the array is a valid permutation:
     static void checkPermutation (int [] ar) {
        int [] b = new int [ar.length];
        int i;
        // check ar valid permutation
        for (i = 0; i < ar.length; i++)
           b[i] = ar[i];
        java.util.Arrays.sort(b);
        for (i = 0; i < b.length; i++)
           if (b[i] != i) {
              System.out.println ("Invalid permutation: " + toString(ar));
              System.exit (1);
           }
     } // end method checkPermutation
• static String toString (int []) - a String representation of the array in a nice format:
     public static String toString (int [] ar) {
        String st = "";
        if (ar == null)
           return st;
        st += ar[0];
        for (int i=1; i < ar.length; i++)
           st += " " + ar[i];
        return st;
     } // end method toString
  
• static String toParanString (int []) - create the parenthesized, cycle, format of a permutation as a String:
     public static String toParanString (int [] ar) {
        int i; // index for looping through elements in permutation
        int n; // index for jumping though a cycle
        String st = "";   // final paran'ed representation, built cycle by cycle
        String st1;       // string for current cycle
       
        int [] b = new int [ar.length];
       
        for (i = 0; i < b.length; i++)  // clears marks for permutation
           b[i] = -1;
        for (i = 0; i < ar.length; i++) {
           if (b[i] == 0)
              continue;    // element already visited
           n = i;
           b[i] = 0;
           st1 = ""; // for cycle represented by one pair of parans
           while (ar[n] != i) {
              st1 = " " + ar[n] + st1; // gets order right
              n = ar[n];               // next element in cycle
              b[n] = 0;               // mark element visited
           } // end while more in permutation
           st += " (" + i + st1 + ")"; // creates cycle and appends to previous cycles
        } // end for each entry
        return st;
     } // end method toParanString
• static int [] nextPermutation (int []) - calculate the next permutation, this code assumes the permutation is valid (no error checking on this point):
  // a [] is an array of n indices, {0, 1, ..., n-1}
  // representing a permutation
  //
  // Operation of algorithm, example - find 6, then 7, then exchange 6 <-> 7 in this case
  //      current: 3 1 2 6 8 7 5 4 0
  //     exchange: 3 1 2 7 8 6 5 4 0
  //      reverse: 3 1 2 7 0 4 5 6 8
  //         next: 3 1 2 7 0 4 5 6 8
  
     public static int [] nextPermutation (int [] ar) {
        int i, t;           // loop index and temporary for swap
        int lim = ar.length - 1; // length of permutation
        int p = 0;          // start of final decreasing sequence - exchange element at p-1
        int [] b  = new int [ar.length];   // result array
       
        // find start of final decreasing sequence
        for (i=0; i < lim; i++)
           if (ar[i] < ar[i+1]) p = i + 1;
    
        // copy first part of sequence directly
        for (i=0; i < p-1; i++)
           b[i] = ar[i];
    
        if (0 == p) t = Integer.MAX_VALUE; // reverese whole list and start over
        else t = ar[p-1];                   // else hold element to be exchanged
    
        for (i = lim; i >= p ; i--) {
           if (ar[i] > t) {            // the exchange element found
              b[p-1] = ar[i];
              ar[i] = t;
              t = Integer.MAX_VALUE;
           } // end if exchange element found
           b[lim - i + p] = ar[i]; // reverse final decreasing sequence to increasing
        } // end for final decreasing sequence
       
        return b;
     } // end method nextPermutation
• static int [] previousPermutation (int []) - calculate the previous permutation in dictionary order:
     public static int [] previousPermutation (int [] ar) {
        int i, t;           // loop index and temporary for swap
        int lim = ar.length - 1; // length of permutation
        int p = 0;          // start of final increasing sequence - exchange element at p-1
        int [] b  = new int [ar.length];   // result array
       
        // find start of final increasing sequence
        for (i=0; i < lim; i++)
           if (ar[i] > ar[i+1]) p = i + 1;
    
        // copy first part of sequence directly
        for (i=0; i < p-1; i++)
           b[i] = ar[i];
    
        if (0 == p) t = Integer.MIN_VALUE; // reverese whole list and start over
        else t = ar[p-1];                   // else hold element to be exchanged
    
        for (i = lim; i >= p ; i--) {
           if (ar[i] < t) {            // the exchange element found
              b[p-1] = ar[i];
              ar[i] = t;
              t = Integer.MIN_VALUE;
           } // end if exchange element found
           b[lim - i + p] = ar[i]; // reverse final increasing sequence to decreasing
        } // end for final increasing sequence
       
        return b;
     } // end method previousPermutation

(end)

Recursive 2:

• Generics:
• This approach uses generics for the ArrayList's, which allows the elements to be String's, for example
• And this approach can be generalized to any permutation of any class of elements.
• The approach below has the children create the path so far, and adds the parent to the 0 position to the returned paths from each child.
• Example - consider the w1 example below (string of a,b,c,d), at the c-b node:
• the children are a and d, so the paths returned are:
  ad and da
• The code in the loop adds b to ad and da
• this recursion then returns bad and bda to the c node
• Paths2 <U> generic class
• simplifies the code somewhat
• toString method - simplifies printing the resulting paths as well.
  

// Walking2.java
// Date: Nov 23, 2017
// Author: Nicholas Duchon.
// Purpose: walk a permutation tree

import java.util.ArrayList;

public class Walking2 <T> {

   void listPaths (ArrayList <T> procs) {
      System.out.println ("Original list: " + procs.toString());

      ArrayList <Path2<T>> paths = walk (procs);
  
      String st = "\npaths:\n";
      for (Path2<T> p: paths) st += p;
      System.out.println (st + "\n");
   } // end method listPaths
  
   ArrayList <Path2<T>> walk (ArrayList <T> todo) {
      ArrayList <Path2<T>> paths = new ArrayList <> ();
     
      if (todo.size() == 1) {
         paths.add (new Path2<T> (todo.get(0)));
         return paths;
      } // end base case
  
      for (int i = 0; i < todo.size(); i++) {
         T p = todo.remove (i);
         for (Path2<T> q: walk (todo)) {
            q.path.add (0, p);
            paths.add (q);
         }
         todo.add (i, p);
      } // end for each element in todo
     
      return paths;
   } // end method walk
     
   public static void main (String [] args) {
      String [] a = {"a", "b", "c", "d"};
      Walking2 <String> w1 = new Walking2 <> ();
      w1.listPaths (new ArrayList <String> (java.util.Arrays.asList (a)));

      String [] b = {"Amy", "Ted", "Bob", "Kat"};
      Walking2 <String> w2 = new Walking2 <> ();
      w2.listPaths (new ArrayList <String> (java.util.Arrays.asList (b)));

      Integer [] c = {1, 2, 3, 4, 5, 6}; // int won't work here
      Walking2 <Integer> w3 = new Walking2 <> ();
      w3.listPaths (new ArrayList <Integer> (java.util.Arrays.asList (c)));

      System.out.println ("bye");
   } // end main
} // end class Walking2

class Path2 <U> {
   ArrayList <U> path = new ArrayList <> ();
  
   public Path2 (U p) {path.add(p);}
  
   public String toString () {
      String st = "\n";
      for (U p: path)
         st += " " + p;
      return st;
   } // end method toString
} // end class Path

Recursive 3:

• This is rather like Walking, but:
• uses generics
• only creates a new path in the child
  

Code:

// File: Walking0.java
// Date: Nov 19, 2017
// Author: Nicholas Duchon.
// Purpose: walking a tree recusively
// History:
//   Sep 18, 2019 - cleaner solution based on Walking.java
//                - generic

import java.util.Scanner;
import java.util.ArrayList;

public class Walking0 <T> {
 
   ArrayList <ArrayList <T>> paths = new ArrayList <> ();

   Walking0 (ArrayList <T> path) {
      walk (path, new ArrayList <T> ());
      System.out.println (toString());
   } // end constructor
 
   void walk (ArrayList <T> children, ArrayList <T> path) {
      // base case - we have reached a leaf node, a path
      if (children.size() == 0) {
         paths.add (new ArrayList <> (path));
         return;
      } // end if leaf
  
      for (int i = 0; i < children.size(); i++) {
         // get the i-th child
         T target = children.remove (i);
         path.add (target);
         walk (children, path);
         path.remove (target);
         // return the i-th child to its previous position
         children.add (i, target);
      } // end for each child
  
   } // end method walk
 
   public String toString () {
      String st = "";
      st += "-- Number of permutations: " + paths.size();
  
      for (ArrayList <T> p: paths) {
         st += "\n";
         for (T i: p)
            st += " " + i;
      } //end for each path
      return st;
   } // end method toString
 
   public static void main (String args []) {
      Scanner stin = new Scanner (System.in);
      System.out.print ("Number of elements: ");
      int n = stin.nextInt ();
      ArrayList <Integer> a = new ArrayList <> ();
      for (int i = 0; i < n; i++) a.add (i);
      Walking0 <Integer> w = new Walking0 <> (a);
     
      System.out.println ("strings:");
      ArrayList <String> b = new ArrayList <> ();
      String [] sa = {"a", "c", "F", "+"};
      for (String s: sa) b.add (s);
      Walking0 <String> w2 = new Walking0 <> (b);
   } // end main
} // end class Walking