Permutations - notes and programs

Places:

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

0 1 2 3
0 1 3 2
0 2 1 3
0 2 3 1
0 3 1 2
0 3 2 1
1 0 2 3
1 0 3 2
1 2 0 3
1 2 3 0
1 3 0 2
1 3 2 0
2 0 1 3
2 0 3 1
2 1 0 3
2 1 3 0
2 3 0 1
2 3 1 0
3 0 1 2
3 0 2 1
3 1 0 2
3 1 2 0
3 2 0 1
3 2 1 0

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

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

(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}.

(end)


Recursive 2:

Comments:

// 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:

Comments:

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


updated: Sep 19 2019 by Nicholas Duchon.