Generating all permutation of a character array

Question

After reading so many post of "generating permutation of string", I tried to write it in Java. 1) Take the first character start swapping with rest of the character in the combination.

But when I tried to implement it using recursion it gave me only two string for a string of length 3 :(.

public static void main(String[] args) {
    char a[]= "123".toCharArray();
    printPermutation(a,0);

}
private static void printPermutation(char[] a, int i) {
    if(i==a.length-1)
        System.out.println(new String(a));
    else{
        for(int x=i+1;x<a.length;x++)
        {
            swap(a,i,x);
            printPermutation(a,x );
            swap(a,i,x);
        }
    }
}
private static void swap(char[] a, int i, int x) {
        char t=a[i];
        a[i]=a[x];
        a[x]=t;
    }

I am expecting 6 string to be printed.

expected: 123, 132, 213, 231, 312, 321

For your own sanity and the sanity of those around you, please use better names for your variables! Naming things sensibly can help you spot bugs earlier, as well as making your code easier to read after a break. — JonK, Aug 10 '16 at 16:20
If you remove the if and else clauses, you will get 2 more outputs. Anyway, as JonK said, please use better variable names. Your algorithm is difficult to understand with these names. What does the argument i means in printPermutation method ?? — Egl, Aug 10 '16 at 17:14

score 7 · Accepted Answer · answered Aug 10 '16 at 17:37

The method printPermutation is the core of your recursion. It doesn't capture the start and end indices properly. This is important because you are trying to swap in chunks

Following change should make it work.

public static void main(String[] args) {
    char a[]= "123".toCharArray();
    printPermutation(a, 0, a.length);
}

private static void printPermutation(char[] a, int startIndex, int endIndex) {
    if (startIndex == endIndex)//reached end of recursion, print the state of a
        System.out.println(new String(a));
    else {
        //try to move the swap window from start index to end index
        //i.e 0 to a.length-1
        for (int x = startIndex; x < endIndex; x++) {
            swap(a, startIndex, x);
            printPermutation(a, startIndex + 1, endIndex);
            swap(a, startIndex, x);
        }
    }
}

private static void swap(char[] a, int i, int x) {
    char t = a[i];
    a[i] = a[x];
    a[x] = t;
}

mr.tarsa · Answer 2 · 2016-08-10T18:01:53.153

The general idea of your permutation algorithm is correct, but you forgot to handle some of possible cases there.

First. You should add printPermutation(a, i + 1) before going into loop.

Second. Call printPermutation(a, i + 1) instead of printPermutation(a, x) in the loop.

public static void main(String[] args) {
    char a[]= "1234".toCharArray();
    printPermutation(a, 0);
}

private static void printPermutation(char[] a, int i) {
    if (i == a.length - 1) System.out.println(new String(a));
    else {
        printPermutation(a, i + 1);
        for (int x = i + 1; x < a.length; x++) {
            swap(a, i, x);
            printPermutation(a, i + 1);
            reswap(a, i, x);
        }
    }
}

private static void swap(char[] a, int i, int x) {
    char tmp = a[i];
    a[i] = a[x];
    a[x] = tmp;
}

private static void reswap(char[] a, int i, int x) {
    swap(a, i, x);
}

Generating all permutation of a character array

2 Answers2

Linked