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