Rosen's Permutation Algorithm

PERMUTATION ALGORITHMS

The general purpose permutation algorithm presented here is a Java implementation of the algorithm described by Rosen (Discrete Mathematics and Its Applications).

The "permute" logic contained within this class is extremely elegant and efficient, however it's not particularly self-explanatory, since it's recursive. The program permutes the contents of a copy of the constant string iAlphabet (e.g. "abcd" in the test run).

Output results follow the listing.

//* Permuter
//* Andrew Carson 2006

package www;

public class Permuter {

    public static void main(String[] args) {
        new Permuter("abcd");
    }

    // instance variables
    private int iCount = 0;

    // constructor
    public Permuter(String input) {
        System.out.println("Permuting \"" + input + "\"");
        char[] value = new char[input.length()];
        for (int i = 0; i < input.length(); i++)
            value[i] = input.charAt(i);
        permute(value, 0, input.length());
        System.out.println(">>> found " + iCount
                + " permutations <<<");
    }

    void permute(char[] v, int a, int b) {
        print(v); iCount++;
        for (int i = b - 2; i >= a; i--) {
            for (int j = i + 1; j < b; j++) {
                swap(v, i, j);
                permute(v, i + 1, b);
            }
            rotate(v, i, b);
        }
    }

    void swap(char[] v, int a, int b) {
        char t = v[a];
        v[a] = v[b];
        v[b] = t;
    }

    void rotate(char[] v, int a, int b) {
        char t = v[a];
        for (int i = a; i < b - 1; i++)
            v[i] = v[i + 1];
        v[b - 1] = t;
    }

    void print(char[] v) {
        System.out.println(" - " + new String(v));
    }
}

Permuting "abcd"
 - abcd
 - abdc
 - acbd
 - acdb
 - adbc
 - adcb
 - bacd
 - badc
 - bcad
 - bcda
 - bdac
 - bdca
 - cabd
 - cadb
 - cbad
 - cbda
 - cdab
 - cdba
 - dabc
 - dacb
 - dbac
 - dbca
 - dcab
 - dcba
>>> found 24 permutations <<<