Generating permutations of an int array using java -- error

Question

I am writing a JAVA code to generate all permutations of a integer array. Though I am getting the number of permutations right, the permutations themselves are not correct.

On running I obtain:

Input array Length
3
1
2
3
0Permutation is
1,  2,  3,  
##########################
1Permutation is
1,  3,  2,  
##########################
2Permutation is
3,  1,  2,  
##########################
3Permutation is
3,  2,  1,  
##########################
4Permutation is
1,  2,  3,  
##########################
5Permutation is
1,  3,  2,  
##########################
6  number of permutations obtained
BUILD SUCCESSFUL (total time: 3 seconds)


public class PermulteArray {

    public static int counter = 0;

    public static void Permute(int[] input, int startindex) {
        int size = input.length;

        if (size == startindex + 1) {
            System.out.println(counter + "Permutation is");
            for (int i = 0; i < size; i++) {
                System.out.print(input[i] + ",  ");
            }
            System.out.println();
            System.out.println("##########################");
            counter++;
        } else {
            for (int i = startindex; i < size; i++) {

                int temp = input[i];
                input[i] = input[startindex];
                input[startindex] = temp;
                Permute(input, startindex + 1);
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("Input array Length");
        int arraylength = in.nextInt();
        int[] input = new int[arraylength];
        for (int i = 0; i < arraylength; i++) {
            input[i] = in.nextInt();
        }
        counter = 0;
        Permute(input, 0);
        System.out.println(counter + "  number of permutations obtained");
    }
}

Answer 1

int temp=input[i];
input[i]=input[startindex];
input[startindex]=temp;
Permute(input, startindex+1);

You've swapped an element before calling Permute but you need to swap it back again afterwards to keep consistent positions of elements across iterations of the for-loop.

Answer 2

This is the best solution I have seen so far :

public static void main(String[] args) {
    int[] a = { 1, 2, 3, 4, 5, 6 };
    permute(0, a);
}

public static void permute(int start, int[] input) {
    if (start == input.length) {
        //System.out.println(input);
        for (int x : input) {
            System.out.print(x);
        }
        System.out.println("");
        return;
    }
    for (int i = start; i < input.length; i++) {
        // swapping
        int temp = input[i];
        input[i] = input[start];
        input[start] = temp;
        // swap(input[i], input[start]);

        permute(start + 1, input);
        // swap(input[i],input[start]);

        int temp2 = input[i];
        input[i] = input[start];
        input[start] = temp2;
    }
}