Permutation in Java and C++

C++

from #include<algorithm>

int a[] = {3,4,6,2,1};
int size = sizeof(a)/sizeof(a[0]);
std::sort(a, a+size);
do {
  // print a's elements
} while(std::next_permutation(a, a+size));

JAVA

public class Permute{
    static void permute(java.util.List<Integer> arr, int k){
        for(int i = k; i < arr.size(); i++){
            java.util.Collections.swap(arr, i, k);
            permute(arr, k+1);
            java.util.Collections.swap(arr, k, i);
        }
        if (k == arr.size() -1){
            System.out.println(java.util.Arrays.toString(arr.toArray()));
        }
    }
    public static void main(String[] args){
        Permute.permute(java.util.Arrays.asList(3,4,6,2,1), 0);
    }
}

You take first element of an array (k=0) and exchange it with any element (i) of the array. Then you recursively apply permutation on array starting with second element. This way you get all permutations starting with i-th element. The tricky part is that after recursive call you must swap i-th element with first element back, otherwise you could get repeated values at the first spot. By swapping it back we restore order of elements (basically you do backtracking).

done