Last time on FAIC I implemented a short algorithm that produces a sequence containing every permutation of a given size, such that the sequence is a Hamiltonian tour of the vertices of the n-dimensional permutohedron. That is, the shape you get when you make each vertex have the coordinates of a permutation, and an edge connects two permutations that differ only by a swap of adjacent items.
Since we have an algorithm that produces the same order every time, we can number each ordering; it is convenient to do so starting with zero and going to
n!-1. What I’d like is an algorithm which given
size, the number of items in the permutation, and
index, an integer between zero and
size!-1, gives back the
indexth permutation of length
size, without having to calculate all of them.