In TAOCP 4A, Knuth introduces a sequence of steps which he calls “Algorithm L”. Algorithm L visits all permutations of a sequence of elements, {a_1 ... a_n} in lexicographical order. For example, if we have [3 | 5 | 4 | 3 | 2 | 1] the next element in the sequence is [4 | 1 | 2 | 3 | 3 | 5].
This post recaps the exact steps prescribed by Algorithm L, with two new touches:
- First, it presents an interactive visualisation allowing you to trace each step; and
- Second, it links to the C++ code responsible for the core logic behind this visualisation.
Let’s take look at the animation. It comprises 4 stages.
- Stage 1: Find the leftmost element that breaks the non-decreasing sequence when we traverse from right to left. We’ll call this left-most element the “pivot element”.
- Stage 2: Having found the pivot element, find the smallest element in the non-decreasing sequence that you had just traversed, that is greater than the pivot element. Note that because the sequence is non-decreasing, you can simply do binary search! (Note that when I mention “non-decreasing”, the order is from right to left.)
- Stage 3: Swap the pivot element with the element that you had found in Stage 2.
- Stage 4: Minimise the sequence of all elements to the right of the pivot place. As the sequence is still non-decreasing after the swap, you can simply reverse it.
What’s behind this animation? It’s actually D3.js calling into a Wasm backend, which I created using C++! Here’s the mapping of the stages to the source code.
| Stage Number | Function Name | Description | Source code |
|---|---|---|---|
| 1 | find_pivot_traced |
Finds the pivot that defies non-decreasing sequence when we traverse from right to left | Link |
| 2 | upper_bound_traced |
Given the value of the pivot element found in Step 1, locates the smallest element that is larger than that value. As earlier mentioned, we use binary search (similar to std’s upper_bound’). We reverse the iterators as the non-decreasing sequence is from right-to-left. |
Link |
| 3 | iter_swap |
Swaps pivot element with the element we’ve found using upper_bound_traced. |
Link |
| 4 | reverse_traced |
Uses two pointers: one at start and one at end, swaps them, and brings both pointers closer together. This reverses the order of the already-sorted sequence. | Link |