Task: Given a multiset and an order on it, find all permutations of it in lexicographic order.

Let I be the given multiset, optimally represented as a sorted (by the given order) multiset structure optimized for iterating in order and for passing along one-smaller subsets until emptiness while soon afterwards needing the whole multiset again.

We should render our input (the multiset and the order on it) into an immutable array of all elements of the multiset ordered, as iterating in order over the majority of elements will be utmostly oft.

We need a way to pass one-smaller sub(multi)sets (of sub(multi)sets of sub(multi)sets…) of our given multiset efficiently. Passing along just a copy with one element removed, like by list comprehensions, will do, but will be rather naïve.

An optimal solution would be to store at what position in the permutation the algorithm is and store a mapping from element references (usually indices of array) to what positions are they on.

We may also store prefix as a mutable global array. Storing everything as globals prompts us to get rid of the recurrency and make it all iterative. For that purpose we can make prefix of sorted_multiset indices instead of elements, and store in a boolean variable whether we are at a given moment increasing under caret or moving caret to right and setting to first under caret, or whether we are backtracking-skipping, increasing under caret even if there would be a possibility to advance caret (which we would be just coming back from but that information needs to be conveyed). If i am not wrong, above variables would be enough for a single-loop implementation, maybe even avoiding any extraneous exit points besides usual conditional statements, and one on end.