PermutationsLex.java

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

/*************************************************************************
 *  Compilation:  javac PermutationsLex.java
 *  Execution:    java PermutationsLex N
 *  
 *  Generate all N! permutations of N elements in lexicographic order.
 *
 *  This program is a Java version based on the program Permlex.c
 *  writen by Frank Ruskey and Joe Sawada.
 *  
 *     http://theory.cs.uvic.ca/inf/perm/PermInfo.html
 * 
 *  % java PermutationsLex 3
 *  012
 *  021
 *  102
 *  120
 *  201
 *  210
 *
 *************************************************************************/


public class PermutationsLex {

    public static void show(int[] a) {
        for (int i = 0; i < a.length; i++)
            StdOut.printf("%d", a[i]);
        StdOut.printf("\n");
    } 

    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static boolean hasNext(int[] a) {
        int N = a.length;

        // find rightmost element a[k] that is smaller than element to its right
        int k; 
        for (k = N-2; k >= 0; k--)
            if (a[k] < a[k+1]) break;
        if (k == -1) return false;

        // find rightmost element a[j] that is larger than a[k]
        int j = N-1;
        while (a[k] > a[j])
            j--;
        swap(a, j, k);

        for (int r = N-1, s = k+1; r > s; r--, s++)
            swap(a, r, s);

        return true;
    }

    public static void perm(int N) {

        // initialize permutation
        int[] a  = new int[N];
        for (int i = 0; i < N; i++)
            a[i] = i;

        // print permutations
        show(a);
        while (hasNext(a))
           show(a);
    }


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