Штейнхаус-Джонсон-Троттер алгоритмі:Permutationдарды тізбектеу әдісі

The Steinhaus–Johnson–Trotter algorithm or Johnson–Trotter algorithm, also called plain changes, is an algorithm named after Hugo Steinhaus, Selmer M. Johnson and Hale F. Trotter that generates all of the permutations of 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 permutohedron, a polytope 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.

The sequence of permutations generated by the Steinhaus–Johnson–Trotter algorithm has a natural recursive 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.

The set of all permutations of items may be represented geometrically by a permutohedron, the polytope formed from the convex hull of vectors, the permutations of the vector Although defined in this way in dimensional space, it is actually an dimensional polytope; for example, the permutohedron on four items is a three dimensional polyhedron, the truncated octahedron. 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 of the symmetric group of permutations on 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 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.

A Gray code for numbers in a given radix 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 permutations of the numbers from 1 to may be placed in one to one correspondence with the numbers from 0 to by pairing each permutation with the sequence of numbers that count the number of positions in the permutation that are to the right of value and that contain a value less than (that is, the number of inversions for which is the larger of the two inverted values), and then interpreting these sequences as numbers in the factorial number system, that is, the mixed radix system with radix sequence For instance, the permutation would give the values , , , , and The sequence of these values, , gives the number

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.

The method was known for much of its 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" 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. 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 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.