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

Answer 1

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