# JohnsonTrotter.java

Below is the syntax highlighted version of JohnsonTrotter.java from §2.3 Recursion.

```/******************************************************************************
*  Compilation:  javac JohnsonTrotter.java
*  Execution:    java JohnsonTrotter n
*
*  Generate permutations by transposing adjacent elements using the
*  Johnson-Trotter algorithm.
*
*  This program is a Java version based on the program SJT.c
*  writen by Frank Ruskey.
*
*     http://theory.cs.uvic.ca/inf/perm/PermInfo.html
*
*  % java JohnsonTrotter 3
*  012   (2 1)
*  021   (1 0)
*  201   (2 1)
*  210   (0 1)
*  120   (1 2)
*  102   (0 1)
*
******************************************************************************/

public class JohnsonTrotter {

public static void perm(int n) {
int[] p   = new int[n];     // permutation
int[] pi  = new int[n];     // inverse permutation
int[] dir = new int[n];     // direction = +1 or -1
for (int i = 0; i < n; i++) {
dir[i] = -1;
p[i]  = i;
pi[i] = i;
}
perm(0, p, pi, dir);
StdOut.printf("   (0 1)\n");
}

public static void perm(int n, int[] p, int[] pi, int[] dir) {

// base case - print out permutation
if (n >= p.length) {
for (int i = 0; i < p.length; i++)
StdOut.print(p[i]);
return;
}

perm(n+1, p, pi, dir);
for (int i = 0; i <= n-1; i++) {

// swap
StdOut.printf("   (%d %d)\n", pi[n], pi[n] + dir[n]);
int z = p[pi[n] + dir[n]];
p[pi[n]] = z;
p[pi[n] + dir[n]] = n;
pi[z] = pi[n];
pi[n] = pi[n] + dir[n];

perm(n+1, p, pi, dir);
}
dir[n] = -dir[n];
}

public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
perm(n);
}
}
```