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,
`i`such that_{1}`ar[i`is the first of a pair of elements in ascending order._{1}]

If there isn’t one, the sequence is the highest permutation, so reverse the whole thing to begin again. - Find the highest index
`i`, such that_{2}`i`>_{2}`i`and_{1}`ar[i`>_{2}]`ar[i`._{1}] - Swap
`ar[i`and_{1}]`ar[i`._{2}] - The elements from
`ar[i`to the end are now in descending order (a later permutation), so reverse them._{1}+ 1]

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