The permutations of a set are the ways of arranging its elements.
For example, there are 24 permutations of a set of 4 elements:
[0, 1, 2, 3] [0, 1, 3, 2] [0, 2, 1, 3] [0, 2, 3, 1] [0, 3, 1, 2] [0, 3, 2, 1] [1, 0, 2, 3] [1, 0, 3, 2] [1, 2, 0, 3] [1, 2, 3, 0] [1, 3, 0, 2] [1, 3, 2, 0] [2, 0, 1, 3] [2, 0, 3, 1] [2, 1, 0, 3] [2, 1, 3, 0] [2, 3, 0, 1] [2, 3, 1, 0] [3, 0, 1, 2] [3, 0, 2, 1] [3, 1, 0, 2] [3, 1, 2, 0] [3, 2, 0, 1] [3, 2, 1, 0]
To find the next permutation of an array ar:
- Find the highest index, i1 such that ar[i1] is the first of a pair of elements in ascending order.
If there isn’t one, the sequence is the highest permutation, so reverse the whole thing to begin again. - Find the highest index i2, such that i2 > i1 and ar[i2] > ar[i1].
- Swap ar[i1] and ar[i2].
- The elements from ar[i1 + 1] to the end are now in descending order (a later permutation), so reverse them.
static void swap(unsigned int *ar, unsigned int first, unsigned int second) { unsigned int temp = ar[first]; ar[first] = ar[second]; ar[second] = temp; } static void reverse(unsigned int *ar, size_t len) { unsigned int i, j; for (i = 0, j = len - 1; i < j; i++, j--) { swap(ar, i, j); } } unsigned int next_permutation(unsigned int *ar, size_t len) { unsigned int i1, i2; unsigned int result = 0; /* Find the rightmost element that is the first in a pair in ascending order */ for (i1 = len - 2, i2 = len - 1; ar[i2] <= ar[i1] && i1 != 0; i1--, i2--); if (ar[i2] <= ar[i1]) { /* If not found, array is highest permutation */ reverse(ar, len); } else { /* Find the rightmost element to the right of i1 that is greater than ar[i1] */ for (i2 = len - 1; i2 > i1 && ar[i2] <= ar[i1]; i2--); /* Swap it with the first one */ swap(ar, i1, i2); /* Reverse the remainder */ reverse(ar + i1 + 1, len - i1 - 1); result = 1; } return result; }