then in ascending order for the permutation 2 1: The same placement pattern, alternating between descending and ascending placements of , applies for any larger value of . 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 , 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 the first and final elements of the sequence, also, differ in only two adjacent elements (the positions of the numbers and ), as may be proven by induction. This sequence may be generated by a recursive algorithm 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 . 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 the sequence starts with , then flips with its left neighbor to get . From this point, flipping with its right neighbor would yield the initial permutation , so the sequence instead flips with its left neighbor and arrives at , 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. Original version As described by , the algorithm for generating the next permutation from a given permutation performs the following steps. For each from 1 to , let be the position where the value is placed in permutation . If the order of the numbers from 1 to in permutation defines an even permutation, let otherwise, let . Find the largest number for which defines a valid position in permutation that contains a number smaller than . Swap the values in positions and . When no number can be found meeting the conditions of the second step of the algorithm, the algorithm