An Ordered Lexicographic Permutation Algorithm based on one published in Practical Algorithms in C++

The next permutation algorithm produces the permutations in lexicographic (or sorted) order. Here we assume that there is a defined ordering between the elements in the set, which can define a sorting order. For example, in the set {1, 2, 3} the sorting order is 1 < 2 < 3 or in the set {a b c}, a < b < c.

The algorithm is diagrammed below for a set of four objects. The algorithm recursively calculates the permutations of larger and larger subsets of the set (e.g., a set of two elements, a set of three elements...}. There is a cost incurred when the permuation is produced in lexicographic order. After each recursive step, the subset is rotated back into the original order in the preceeding stage. The time complexity of this reordering appears to be similar to the cost that would be incurred by sorting the final permutation set, so this reordering may not be justified.