Permutation
Generation in lexicographic order

There are many ways to systematically generate all permutations of a given sequence. 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 Pandita in 14th century India, and has been rediscovered frequently.

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

For example, given the sequence (which is in increasing order), and given that the index is zero-based, the steps are as follows:

Following this algorithm, the next lexicographic permutation will be, and the 24th permutation will be at which point a < a 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.
change_case:capital_word_frequency[8]