Print All Permutations of Sets
A permutation of a set is an arrangement of the elements in a particular order. For example, there are two permutations of {1,2}, namely {1,2} and {2,1}, and 6 permutations of {1,2,3}, namely {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, and {3,2,1}. In general, the number of permutations for a set of n elements is n! = n·(n-1)···2·1.
The following code uses backtracking to print all permutations. We assume the input array has no duplicates, that is, it represents a set. The algorithm runs in time O(n*n!).
public static void swap(int[] arr, int i, int j)
{
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void permute(int[] arr, int i)
{
if (i == arr.length)
{
System.out.println(Arrays.toString(arr));
return;
}
for (int j = i; j <= arr.length; j++)
{
swap(arr, i, j); // enumerates on position i
permute(arr, i + 1); // recurse
swap(arr, i, j); // backtracking
}
}
......
int[] arr = {1, 2, 3};
permute(arr, 0);
When we call permute(arr, 0), the loop enumerates all possible ways of fixing the first position. The first swap changes the value at the first position, and the final swap recovers the original value. For each value of the first position, the recursive call works on the subarray starting from the second position.