has reached the final permutation of the sequence and terminates. This procedure may be implemented in time per permutation. gives an alternative implementation of an iterative algorithm for the same sequence, in lightly commented ALGOL 60 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 are: When all numbers become unmarked, the algorithm terminates. This algorithm takes time for every step in which the greatest number to move is . Thus, the swaps involving the number take only constant time; since these swaps account for all but a 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 allows it to be performed in constant time per permutation in every case; however, the modifications