Generating Permutations and Subsets
Exhaustive search needs a way to list every candidate exactly once. Here are five generators: three for the n! permutations and two for the 2ⁿ subsets. The best ones make a minimal change between neighbors: one swap, or one bit.
How to read this
Tiles. Each tile is one element of the current permutation (or one bit of the current bit string). Yellow tiles are being examined (a decreasing suffix, or the mobile elements), blue is the chosen element, red tiles were just swapped or flipped, purple marks a second chosen position (lexicographic j) or arrows that were just reversed.
Johnson–Trotter arrows. Each element points left or right. An element is mobile if its arrow points at a smaller neighbor. The largest mobile element moves one step; then every larger element turns around.
Subsets as bit strings. Bit bᵢ = 1 means item aᵢ is in the subset. The cube on the right has one corner per bit string (n ≤ 4); two corners are joined when they differ in exactly one bit. Gray code walks along cube edges. Binary counting sometimes jumps across the cube (dashed red), changing many bits at once.
Generated so far lists every object in output order. The counters compare the total count with n! or 2ⁿ.
Try this
- Minimal-change insertion with n = 3 should give 123, 132, 312, 321, 231, 213 (Levitin Fig. 4.9). Now run Johnson–Trotter with n = 3: same list, no smaller lists needed.
- Lexicographic: start from 3 6 2 5 4 1. The next permutation is 3 6 4 1 2 5. Watch the three moves: find i, find j, swap, reverse.
- Binary counting with n = 4: how many bits flip going from 0111 to 1000? Look at the "most bits changed" counter. Gray code never flips more than one.
- Gray code with n = 3: follow the walk on the cube. Does the last corner (100) connect back to the first (000)? That makes the code cyclic.
- Set n = 6 in Johnson–Trotter and play at full speed. 720 permutations, each one swap away from the last. At n = 25 there would be about 1.55 × 10²⁵ of them.