Permutation generation Created 2026-10-31 Updated 2026-11-05
Permutation generation enumerates arrangements of a finite collection under a stated convention. For distinct labelled objects there are permutations, so explicitly writing every length- arrangement already requires output work. Permutation generation by insertion builds each arrangement from a shorter one; the Steinhaus-Johnson-Trotter algorithm instead changes only an adjacent transposition between consecutive arrangements. Repeated values require deciding whether positions remain distinguishable. For values
a,a,b, there are six permutations of labelled positions but only three distinct value strings. Steinhaus-Johnson-Trotter algorithm Created 2026-10-20 Updated 2026-11-05
The Steinhaus-Johnson-Trotter algorithm lists all permutations so consecutive entries differ by one adjacent transposition. Start at increasing order with an arrow pointing left on each label. A label is mobile if its arrow points to an adjacent smaller label. Swap the largest mobile label in its arrow direction, then reverse the arrows of every larger label; stop when none is mobile. For three labels this gives
123, 132, 312, 321, 231, 213. Recursively, the largest label sweeps across each smaller-label arrangement in alternating directions, visiting every insertion position once. This gives a Gray code on permutations, useful when an objective can be updated cheaply after a local exchange.