Permutations

Overview

A permutation of some $n$ objects is a (possible) rearrangement of those $n$ objects. The number of permutations is $n!$ since there are $n$ possible ways to pick the first object, $(n-1)$ possible ways to pick the second, and so on.

void next(const size_t n, int A[static n]) {
  size_t pivot = -1;
  for (size_t i = n - 1; i >= 1; --i) {
    if (A[i - 1] < A[i]) {
      pivot = i - 1;
      break;
    }
  }
  if (pivot == -1) {
    reverse(0, n - 1, A);
    return;
  }
  size_t j = pivot;
  for (size_t i = pivot + 1; i < n; ++i) {
    if (A[pivot] < A[i] && (j == pivot || A[i] < A[j])) {
      j = i;
    }
  }
  swap(pivot, j, A);
  reverse(pivot + 1, n - 1, A);
}
 
void permutations(const size_t n, int A[static n]) {
  size_t iters = factorial(n);
  for (size_t i = 0; i < iters; ++i) {
    print_array(n, A);
    next(n, A);
  }
}

The above approach prints out all permutations of an array (assuming distinct values).

Lexicographic Ordering

We can find the next lexicographic ordering of an array via a procedure of “pivot”, “swap”, and “reverse”. The function void next(const size_t n, int A[static n]) defined in Overview shows the details, taking in a permutation and producing the next, lexicographically speaking. To prove correctness, consider the following:

[ a₁ a₂ ... aᵢ | aᵢ₊₁ aᵢ₊₂ ... aₙ ]

Here the RHS side is the longest increasing sequence we could find, from right to left. That is, $a_{i+1}>a_{i+2}>\cdots >a_n$. Denote $a_i$ as the pivot. Next, swap the smallest element in the RHS greater than $a_i$, say $a_j$, with $a_i$. This produces

[ a₁ a₂ ... aⱼ | aᵢ₊₁ aᵢ₊₂ ... aᵢ ... aₙ ]

Notice the RHS remains in sorted order. Since $a_j$ was the next smallest element, reversing the reverse-sorted RHS produces the next permutation, lexicographically speaking:

[ a₁ a₂ ... aⱼ | aₙ ... aᵢ ... aᵢ₊₂ aᵢ₊₁ ]

Eventually the swapped $a_j$ will be the largest in the RHS ensuring that the breakpoint will eventually move one more position leftward.

Falling Factorials

If we generalize to choosing $k\le n$ elements of $n$ objects, we can calculate the $k$-permutation of $n$. This is denoted as $(n{)}_k$, sometimes called the falling factorial. $(n{)}_k=\frac{n!}{(n-k)!}$

The derivation works by noting that we have $n-0$ possible ways to pick the first object, $n-1$ ways to pick the second, up until $n-(k-1)$ ways to pick the last object.

Bibliography

• Gries, David. The Science of Programming. Texts and Monographs in Computer Science. New York: Springer-Verlag, 1981.
• Oscar Levin, Discrete Mathematics: An Open Introduction, 3rd ed., n.d., https://discrete.openmathbooks.org/pdfs/dmoi3-tablet.pdf.