ordering for the objects in which each two consecutive objects differ in the minimal possible way. In this generalized sense, the Steinhaus–Johnson–Trotter algorithm generates a Gray code for the permutations themselves. History The method was known for much of history as a method for change ringing of church bells: it gives a procedure by which a set of bells can be rung through all possible permutations, changing the order of only two bells per change. These so-called "plain changes" were recorded as early as 1621 for four bells, and a 1677 book by Fabian Stedman lists the solutions for up to six bells. More recently, change ringers have abided by a rule that no bell may stay in the same position for three consecutive permutations; this rule is violated by the plain changes, so other strategies that swap multiple bells per change have been devised. The algorithm is named after Hugo Steinhaus, Selmer M. Johnson and Hale F. Trotter. Johnson and Trotter rediscovered the algorithm independently of each other in the early 1960s. A book by Steinhaus, originally published in 1958 and translated into English in 1963, describes a related puzzle of generating all permutations by a system of particles, each moving at constant speed along a line and swapping positions when one particle overtakes another. No solution is possible for , because the number of swaps is far fewer than the number of permutations, but the Steinhaus–Johnson–Trotter algorithm describes the motion of particles with non-constant speeds that generate all permutations. See also Heap's algorithm, a different method for listing all permutations Fisher–Yates shuffle, a method for generating random permutations Notes References . Although Dijkstra does not cite any prior literature, an earlier draft EWD502 reveals that he knew of . ; see Section 2.1, "A minimum-change generator", pp. 3–8 Combinatorial algorithms Permutations