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. Articles by others on the same topic
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.