The lexicographical permutations of a list with n elements can be numbered from 0 to n! - 1. For example, the 3! = 6 permutations of
(1,2,3) would be
When a permutation is applied to a list, its elements are ordered in the same order as the numbers in the permutation. For example, applying the permutation
l = (a,b,c) yields
(l,l,l) = (b,c,a).
The inverse of a permutation is defined as the permutation that reverses this operation, i.e. applying a permutation and then its inverse (or vice versa) does not modify the array. For example, the inverse of
(3,1,2), since applying that to
Also, a permutation's inverse applied to the permutation itself yields the integers 1…n. For example, applying
We now define the function revind(x) as the index of the inverse permutation of the permutation with index x. (This is A056019, if you're interested.)
Since a permutation with index i only modifies the last k items of the list iff 0 ≤ i < k!, we can add any number of elements to the start of the list without affecting revind(i). Therefore the length of the list does not affect the result.
Your task is to implement revind(x). You will write a full program or function that takes a single nonnegative integer x as input/argument and outputs/returns the result as a single nonnegative integer.
The input and output may be 0-indexed or 1-indexed, but this must be consistent between them.
Builtins that generate permutations by index, return the index of a permutation or find the inverse permutation are banned. (Builtins that generate all permutations or the next permutation are allowed.)
Standard code-golf rules apply.
The examples below are 0-indexed.
Input Output 0 0 1 1 2 2 3 4 4 3 5 5 6 6 13 10 42 51 100 41 1000 3628 2000 3974 10000 30593 100000 303016
Reference implementation (Python 3)
def revind(n): from math import factorial from itertools import permutations, count l = next(filter(lambda x: factorial(x) > n, count(1))) pms = list(permutations(range(l))) return [k for k in range(len(pms)) if tuple(pms[n][i] for i in pms[k]) == pms]