## Permutations - notes and programs |
## Places: |

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.

- 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: 1 2 3 6 8 7 5 4 0

next: 1 2 3 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: 1 2 3

6 8 7 5 4 0

next: 1 2 3 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: 1 2 3

6 8 7 5 4 0

exchange: 1 2 37 8 6 5 4 0

reverse: 1 2 37 0 4 5 6 8

next: 1 2 3 7 0 4 5 6 8

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

- 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)

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: 1 2 3 6 8 7 5 4 0

// exchange: 1 2 3 7 8 6 5 4 0

// reverse: 1 2 3 7 0 4 5 6 8

// next: 1 2 3 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)

updated: Nov 19, 2017 by Nicholas Duchon.