Search
View source code
Display the source code in std/algorithm/sorting.d from which this page was generated on github.
Report a bug
Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using local clone.

# Function `std.algorithm.sorting.nthPermutation`

Permutes `range` into the `perm` permutation.

``` ref Range nthPermutation(Range) (   auto ref Range range,   const ulong perm ) if (isRandomAccessRange!Range && hasLength!Range); ```

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];
```

## Returns

The permuted range.

## Parameters

NameDescription
range The Range to permute. The original ordering will be lost.
perm The permutation to permutate `range` to.

## Example

``````auto src = [0, 1, 2, 3, 4, 5, 6];
auto rslt = [4, 0, 6, 2, 1, 3, 5];

src = nthPermutation(src, 2982);
writeln(src); // rslt
``````