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.



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)


updated: Nov 19, 2017 by Nicholas Duchon.