nthPermutation

Permutes range into the perm permutation.

The algorithm has a constant runtime complexity with respect to the number of permutations created. Due to the number of unique values of ulong only the first 21 elements of range can be permuted. The rest of the range will therefore not be permuted. This algorithm uses the Lehmer Code.

The algorithm works as follows:

   auto pem = [4,0,4,1,0,0,0]; // permutation 2982 in factorial
auto src = [0,1,2,3,4,5,6]; // the range to permutate
auto i = 0;                    // range index // range index iterates pem and src in sync // pem[i] + i is used as index into src // first src[pem[i] + i] is stored in t auto t = 4;                    // tmp value src = [0,1,2,3,n,5,6];
// then the values between i and pem[i] + i are moved one // to the right src = [n,0,1,2,3,5,6]; // at last t is inserted into position i src = [4,0,1,2,3,5,6]; // finally i is incremented ++i;
// this process is repeated while i < pem.length
t = 0; src = [4,n,1,2,3,5,6]; src = [4,0,1,2,3,5,6]; ++i; t = 6; src = [4,0,1,2,3,5,n]; src = [4,0,n,1,2,3,5]; src = [4,0,6,1,2,3,5];