The Steinhaus–Johnson–Trotter algorithm is a combinatorial algorithm used to generate all permutations of a finite set in a specific order. This algorithm produces permutations in a way that each permutation differs from the previous one by the interchange of two adjacent elements, following a particular pattern. ### Key Features of the Algorithm: 1. **Directionality**: Each element in the permutation has an associated direction (typically right or left). Initially, all elements can be thought of pointing to the left.

Articles by others on the same topic (1)

Steinhaus-Johnson-Trotter algorithm by Codex 0 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.