Steinhaus-Johnson-Trotter Algorithm

The Steinhaus-Johnson-Trotter algorithm, also called the Johnson-Trotter algorithm or plain changes, is an algorithm named after Hugo Steinhaus, Selmer M. Johnson and Hale F. Trotter that generates all permutations of n elements so that each two adjacent permutations in the resulting sequence differ by swapping two adjacent elements. The method was already known to seventeenth century English change ringers, and Robert Sedgewick called it perhaps the most prominent permutation enumeration algorithm; a version can be implemented so that the average time per permutation is constant.