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
- 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:
Comments:
- 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:
Comments:
- 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
updated: Sep 19 2019 by Nicholas Duchon.