Steinhaus–Johnson–Trotter Algorithm
   HOME

TheInfoList



OR:

The Steinhaus–Johnson–Trotter algorithm or Johnson–Trotter algorithm, also called plain changes, is an
algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
named after
Hugo Steinhaus Hugo Dyonizy Steinhaus ( , ; 14 January 1887 – 25 February 1972) was a Polish mathematician and educator. Steinhaus obtained his PhD under David Hilbert at Göttingen University in 1911 and later became a professor at the Jan Kazimierz Univers ...
,
Selmer M. Johnson Selmer Martin Johnson (21 May 1916 – 26 June 1996) was an American mathematician, a researcher at the RAND Corporation. Biography Johnson was born on May 21, 1916, in Buhl, Minnesota. He earned a B.A. and then an M.A. in mathematics from the ...
and Hale F. Trotter that generates all of the
permutation In mathematics, a permutation of a set can mean one of two different things: * an arrangement of its members in a sequence or linear order, or * the act or process of changing the linear order of an ordered set. An example of the first mean ...
s of n elements. Each two adjacent permutations in the resulting sequence differ by swapping two adjacent permuted elements. Equivalently, this algorithm finds a
Hamiltonian cycle In the mathematics, mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path (graph theory), path in an undirected or directed graph that visits each vertex (graph theory), vertex exactly once. A Hamiltonian cycle (or ...
in the
permutohedron In mathematics, the permutohedron (also spelled permutahedron) of order is an -dimensional polytope embedded in an -dimensional space. Its vertex (geometry), vertex coordinates (labels) are the permutations of the first natural numbers. The edg ...
, a
polytope In elementary geometry, a polytope is a geometric object with flat sides ('' faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an ...
whose vertices represent permutations and whose edges represent swaps. This method was known already to 17th-century English change ringers, and Robert Sedgewick calls it "perhaps the most prominent permutation enumeration algorithm". A version of the algorithm can be implemented in such a way that the average time per permutation is constant. As well as being simple and computationally efficient, this algorithm has the advantage that subsequent computations on the generated permutations may be sped up by taking advantage of the similarity between consecutive permutations.


Algorithm

The sequence of permutations generated by the Steinhaus–Johnson–Trotter algorithm has a natural
recursive Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in m ...
structure, that can be generated by a recursive algorithm. However the actual Steinhaus–Johnson–Trotter algorithm does not use recursion, instead computing the same sequence of permutations by a simple iterative method. A later improvement allows it to run in constant average time per permutation.


Recursive structure

The sequence of permutations for a given number n can be formed from the sequence of permutations for n-1 by placing the number n into each possible position in each of the shorter permutations. The Steinhaus–Johnson–Trotter algorithm follows this structure: the sequence of permutations it generates consists of (n-1)! blocks of permutations, so that within each block the permutations agree on the ordering of the numbers from 1 to n-1 and differ only in the position of n. The blocks themselves are ordered recursively, according to the Steinhaus–Johnson–Trotter algorithm for one less element. Within each block, the positions in which n is placed occur either in descending or ascending order, and the blocks alternate between these two orders: the placements of n in the first block are in descending order, in the second block they are in ascending order, in the third block they are in descending order, and so on.; , section 3; . Thus, from the single permutation on one element, one may place the number 2 in each possible position in descending order to form a list of two permutations on two elements, Then, one may place the number 3 in each of three different positions for these two permutations, in descending order for the first permutation 1 2, and then in ascending order for the permutation 2 1: The same placement pattern, alternating between descending and ascending placements of n, applies for any larger value of n. In sequences of permutations with this recursive structure, each permutation differs from the previous one either by the single-position-at-a-time motion of n, or by a change of two smaller numbers inherited from the previous sequence of shorter permutations. In either case this difference is just the transposition of two adjacent elements. When n > 1 the first and final elements of the sequence, also, differ in only two adjacent elements (the positions of the numbers 1 and 2), as may be proven by induction. This sequence may be generated by a
recursive algorithm In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves ...
that constructs the sequence of smaller permutations and then performs all possible insertions of the largest number into the recursively-generated sequence. The same ordering of permutations can also be described equivalently as the ordering generated by the following greedy algorithm. Start with the identity permutation 1\;2\;\ldots\;n. Now repeatedly transpose the largest possible entry with the entry to its left or right, such that in each step, a new permutation is created that has not been encountered in the list of permutations before. For example, in the case n=3 the sequence starts with 1\;2\;3, then flips 3 with its left neighbor to get 1\;3\;2. From this point, flipping 3 with its right neighbor 2 would yield the initial permutation 1\;2\;3, so the sequence instead flips 3 with its left neighbor 1 and arrives at 3\;1\;2, etc. The direction of the transposition (left or right) is always uniquely determined in this algorithm. However, the actual Steinhaus–Johnson–Trotter algorithm does not use recursion, and does not need to keep track of the permutations that it has already encountered. Instead, it computes the same sequence of permutations by a simple
iterative method In computational mathematics, an iterative method is a Algorithm, mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the ''i''-th approximation (called an " ...
.


Original version

As described by Johnson, the algorithm for generating the next permutation from a given permutation \pi performs the following steps. *For each i from 1 to n, let x_i be the position where the value i is placed in permutation \pi. If the order of the numbers from 1 to i-1 in permutation \pi defines an
even permutation In mathematics, when ''X'' is a finite set with at least two elements, the permutations of ''X'' (i.e. the bijective functions from ''X'' to ''X'') fall into two classes of equal size: the even permutations and the odd permutations. If any total ...
, let y_i=x_i-1 otherwise, let y_i=x_i+1. *Find the largest number i for which y_i defines a valid position in permutation \pi that contains a number smaller than i. Swap the values in positions x_i and y_i. When no number i can be found meeting the conditions of the second step of the algorithm, the algorithm has reached the final permutation of the sequence and terminates. This procedure may be implemented in O(n) time per permutation. Trotter gives an alternative implementation of an iterative algorithm for the same sequence, in lightly commented
ALGOL 60 ALGOL 60 (short for ''Algorithmic Language 1960'') is a member of the ALGOL family of computer programming languages. It followed on from ALGOL 58 which had introduced code blocks and the begin and end pairs for delimiting them, representing a ...
notation. Because this method generates permutations that alternate between being even and odd, it may easily be modified to generate only the even permutations or only the odd permutations: to generate the next permutation of the same parity from a given permutation, simply apply the same procedure twice.


Even's speedup

A subsequent improvement by Shimon Even provides an improvement to the running time of the algorithm by storing additional information for each element in the permutation: its position, and a ''direction'' (positive, negative, or zero) in which it is currently moving (essentially, this is the same information computed using the parity of the permutation in Johnson's version of the algorithm). Initially, the direction of the number 1 is zero, and all other elements have a negative direction: At each step, the algorithm finds the greatest element with a nonzero direction, and swaps it in the indicated direction: If this causes the chosen element to reach the first or last position within the permutation, or if the next element in the same direction is greater than the chosen element, the direction of the chosen element is set to zero: After each step, all elements greater than the chosen element (which previously had direction zero) have their directions set to indicate motion toward the chosen element. That is, positive for all elements between the start of the permutation and the chosen element, and negative for elements toward the end. Thus, in this example, after the number 2 moves, the number 3 becomes marked with a direction again: The remaining two steps of the algorithm for n=3 are: When all numbers become unmarked, the algorithm terminates. This algorithm takes time O(i) for every step in which the greatest number to move is n-i+1. Thus, the swaps involving the number n take only constant time; since these swaps account for all but a 1/n fraction of all of the swaps performed by the algorithm, the average time per permutation generated is also constant, even though a small number of permutations will take a larger amount of time. A more complex loopless version of the same procedure suitable for
functional programming In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declarat ...
allows it to be performed in constant time per permutation in every case; however, the modifications needed to eliminate loops from the procedure make it slower in practice.


Related structures


Permutohedron

The set of all permutations of n items may be represented geometrically by a
permutohedron In mathematics, the permutohedron (also spelled permutahedron) of order is an -dimensional polytope embedded in an -dimensional space. Its vertex (geometry), vertex coordinates (labels) are the permutations of the first natural numbers. The edg ...
, the
polytope In elementary geometry, a polytope is a geometric object with flat sides ('' faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an ...
formed from the
convex hull In geometry, the convex hull, convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, ...
of n! vectors, the permutations of the vector (1,2,\dots n). Although defined in this way in n-dimensional space, it is actually an (n-1)-dimensional polytope; for example, the permutohedron on four items is a three-dimensional polyhedron, the
truncated octahedron In geometry, the truncated octahedron is the Archimedean solid that arises from a regular octahedron by removing six pyramids, one at each of the octahedron's vertices. The truncated octahedron has 14 faces (8 regular hexagon, hexagons and 6 Squa ...
. If each vertex of the permutohedron is labeled by the inverse permutation to the permutation defined by its vertex coordinates, the resulting labeling describes a
Cayley graph In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group, is a Graph (discrete mathematics), graph that encodes the abstract structure of a group (mathematics), group. Its definition is sug ...
of the
symmetric group In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric grou ...
of permutations on n items, as generated by the permutations that swap adjacent pairs of items. Thus, each two consecutive permutations in the sequence generated by the Steinhaus–Johnson–Trotter algorithm correspond in this way to two vertices that form the endpoints of an edge in the permutohedron, and the whole sequence of permutations describes a
Hamiltonian path In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vert ...
in the permutohedron, a path that passes through each vertex exactly once. If the sequence of permutations is completed by adding one more edge from the last permutation to the first one in the sequence, the result is instead a Hamiltonian cycle.


Gray codes

A
Gray code The reflected binary code (RBC), also known as reflected binary (RB) or Gray code after Frank Gray (researcher), Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit). For ...
for numbers in a given
radix In a positional numeral system, the radix (radices) or base is the number of unique digits, including the digit zero, used to represent numbers. For example, for the decimal system (the most common system in use today) the radix is ten, becaus ...
is a sequence that contains each number up to a given limit exactly once, in such a way that each pair of consecutive numbers differs by one in a single digit. The n! permutations of the n numbers from 1 to n may be placed in one-to-one correspondence with the n! numbers from 0 to n!-1 by pairing each permutation with the sequence of numbers c_i that count the number of positions in the permutation that are to the right of value i and that contain a value less than i (that is, the number of inversions for which i is the larger of the two inverted values), and then interpreting these sequences as numbers in the
factorial number system In combinatorics, the factorial number system (also known as factoradic), is a mixed radix numeral system adapted to numbering permutations. It is also called factorial base, although factorials do not function as base, but as place value of ...
, that is, the
mixed radix Mixed radix numeral systems are non-standard positional numeral systems in which the numerical base varies from position to position. Such numerical representation applies when a quantity is expressed using a sequence of units that are each a m ...
system with radix sequence (1,2,3,4,\dots) For instance, the permutation (3,1,4,5,2) would give the values c_1=0, c_2=0, c_3=2, c_4=1, and c_5=1. The sequence of these values, (0,0,2,1,1), gives the number 0\times 0!+0\times 1!+2\times 2!+1\times 3!+1\times 4!=34. Consecutive permutations in the sequence generated by the Steinhaus–Johnson–Trotter algorithm have numbers of inversions that differ by one, forming a Gray code for the factorial number system. More generally, combinatorial algorithms researchers have defined a Gray code for a set of combinatorial objects to be an 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 its history as a method for
change ringing Change ringing is the art of ringing a set of tuning (music), tuned bell (instrument), bells in a tightly controlled manner to produce precise variations in their successive striking sequences, known as "changes". This can be by method ringing in ...
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" or "plain hunt" were known by circa 1621 for four bells, and the general method has been traced to an unpublished 1653 manuscript by
Peter Mundy Peter Mundy (born-1597 ~ 1667) was a seventeenth-century English factor, merchant trader, traveller and writer. He was the first Englishman to record, in his ''Itinerarium Mundi'' ('Itinerary of the World'), tasting ''Tea, Chaa'' (tea) in China ...
. A 1677 book by
Fabian Stedman Fabian Stedman (1640–1713) was an English author and a leading figure in the early history of campanology, particularly in the field of method ringing. He had a key role in publishing two books ''Tintinnalogia'' (1668 with Richard Duckworth) an ...
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 Hugo Dyonizy Steinhaus ( , ; 14 January 1887 – 25 February 1972) was a Polish mathematician and educator. Steinhaus obtained his PhD under David Hilbert at Göttingen University in 1911 and later became a professor at the Jan Kazimierz Univers ...
,
Selmer M. Johnson Selmer Martin Johnson (21 May 1916 – 26 June 1996) was an American mathematician, a researcher at the RAND Corporation. Biography Johnson was born on May 21, 1916, in Buhl, Minnesota. He earned a B.A. and then an M.A. in mathematics from the ...
and Hale F. Trotter. Johnson and Trotter rediscovered the algorithm independently of each other in the early 1960s.; . A 1958 book by Steinhaus, translated into English in 1964, describes a related impossible 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. A 1976 paper by Hu and Bien credited Steinhaus with formulating the algorithmic problem of generating all permutations, and by 1989 his book had been (incorrectly) credited as one of the original publications of the algorithm.


See also

*
Heap's algorithm Heap's algorithm generates all possible permutations of objects. It was first proposed by B. R. Heap in 1963. The algorithm minimizes movement: it generates each permutation from the previous one by interchanging a single pair of elements; th ...
, a different method for listing all permutations *
Fisher–Yates shuffle The Fisher–Yates shuffle is an algorithm for shuffling a finite sequence. The algorithm takes a list of all the elements of the sequence, and continually determines the next element in the shuffled sequence by randomly drawing an element from th ...
, a method for generating random permutations


Notes


References

* * *. Although Dijkstra does not cite any prior literature, an earlier draf
EWD502
reveals that he knew of . * * * * *; see Section 2.1, "A minimum-change generator", pp. 3–8 * * * * * * * * * * {{DEFAULTSORT:Steinhaus-Johnson-Trotter algorithm Combinatorial algorithms Permutations