Editing Permutation (section)

====Generation in lexicographic order====
There are many ways to systematically generate all permutations of a given sequence.<ref name=sedegewick1977>{{cite journal
|last=Sedgewick|first=R
|title=Permutation generation methods
|journal=Computing Surveys|year=1977|volume=9
|issue=2
|pages=137–164
|url=http://www.math.uiowa.edu/~goodman/22m150.dir/2007/Permutation%20Generation%20Methods.pdf |archive-url=https://web.archive.org/web/20080221185652/http://www.math.uiowa.edu/~goodman/22m150.dir/2007/Permutation%20Generation%20Methods.pdf |archive-date=2008-02-21 |url-status=live
|doi=10.1145/356689.356692
|s2cid=12139332
}}</ref>
One classic, simple, and flexible algorithm is based upon finding the next permutation in [[lexicographic ordering]], if it exists. It can handle repeated values, for which case it generates each distinct multiset permutation once. Even for ordinary permutations it is significantly more efficient than generating values for the Lehmer code in lexicographic order (possibly using the [[factorial number system]]) and converting those to permutations. It begins by sorting the sequence in (weakly) [[increasing]] order (which gives its lexicographically minimal permutation), and then repeats advancing to the next permutation as long as one is found. The method goes back to [[Narayana Pandit]]a in 14th century India, and has been rediscovered frequently.{{sfn|Knuth|2005|pp=1–26}}

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

# Find the largest index ''k'' such that {{math|''a''[''k''] < ''a''[''k'' + 1]}}.  If no such index exists, the permutation is the last permutation.
# Find the largest index ''l'' greater than ''k'' such that {{math|''a''[''k''] < ''a''[''l'']}}.
# Swap the value of ''a''[''k''] with that of ''a''[''l''].
# Reverse the sequence from ''a''[''k'' + 1] up to and including the final element ''a''[''n''].
For example, given the sequence [1, 2, 3, 4] (which is in increasing order), and given that the index is [[Zero-based numbering|zero-based]], the steps are as follows:
# Index ''k'' = 2, because 3 is placed at an index that satisfies condition of being the largest index that is still less than ''a''[''k'' + 1] which is 4.
# Index ''l'' = 3, because 4 is the only value in the sequence that is greater than 3 in order to satisfy the condition ''a''[''k''] < ''a''[''l''].
# The values of ''a''[2] and ''a''[3] are swapped to form the new sequence [1, 2, 4, 3].
# The sequence after ''k''-index ''a''[2] to the final element is reversed. Because only one value lies after this index (the 3), the sequence remains unchanged in this instance. Thus the lexicographic successor of the initial state is permuted: [1, 2, 4, 3].
Following this algorithm, the next lexicographic permutation will be [1, 3, 2, 4], and the 24th permutation will be [4, 3, 2, 1] at which point ''a''[''k''] < ''a''[''k'' + 1] does not exist, indicating that this is the last permutation.

This method uses about 3 comparisons and 1.5 swaps per permutation, amortized over the whole sequence, not counting the initial sort.<ref>{{cite web|title=std::next_permutation|url=http://en.cppreference.com/w/cpp/algorithm/next_permutation|access-date=31 March 2018|work=cppreference.com|date=4 December 2017}}</ref>