Inverse permutation index

Question

Introduction

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 (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).

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 (2,3,1) to l = (a,b,c) yields (l[2],l[3],l[1]) = (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 (2,3,1) is (3,1,2), since applying that to (b,c,a) yields (a,b,c).

Also, a permutation's inverse applied to the permutation itself yields the integers 1…n. For example, applying (3,1,2) to (2,3,1) yields (1,2,3).

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.

Challenge

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.

Examples

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[0]][0]

Answer 1

Jelly, 6 bytes

ịŒ!⁺iR

I/O uses 1-based indexing. Very slow and memory-hungry.

Verification

As long as the input does not exceed 8! = 40320, it is sufficient to consider all permutations of the array [1, …, 8]. For the last test case, the permutations of [1, …, 9] suffice.

With slightly modified code that only considers the permutations of the first 8 or 9 positive integers, you can Try it online! or verify all remaining test cases.

How it works

ịŒ!⁺iR  Main link. Argument: n

 Œ!     Yield all permutations of [1, ..., n].
ị       At-index; retrieve the n-th permutation.
   ⁺    Duplicate the Œ! atom, generating all permutations of the n-th permutation.
     R  Range; yield [1, ..., n].
    i   Index; find the index of [1, ..., n] in the generated 2D array.

Alternate approach, 6 bytes (invalid)

Œ!Ụ€Ụi

It's just as long and it uses the forbidden grade up atom Ụ, but it's (arguably) more idiomatic.

By prepending 8 (or 9 for the last test case), we can actually Try it online!

How it works

Œ!Ụ€Ụi  Main link. Argument: n

Œ!      Yield all permutations of [1, ..., n].
  Ụ€    Grade up each; sort the indices of each permutation by the corresponding
        values. For a permutation of [1, ..., n], this inverts the permutation.
    Ụ   Grade up; sort [1, ..., n!] by the corresponding inverted permutations
        (lexicographical order).
     i  Index; yield the 1-based index of n, which corresponds to the inverse of
        the n-th permutation.

Answer 2

Mathematica, 74 bytes

Max@k[i,Flatten@Outer[i=Permutations[j=Range@#];k=Position,{i[[#]]},j,1]]&

Uses 1-indexing. Very inefficient. (uses ~11GB of memory when the input is 11)

Explanation

j=Range@#

Generate a list from 1 to N. Store that in j.

i=Permutations[...]

Find all permutations of j. Store that in i.

k=Position

Store the Position function in k. (to reduce byte-count when using Position again)

Flatten@Outer[...,{i[[#]]},j,1]

Find the inverse permutation of the N-th permutation.

Max@k[i,...]

Find the k (Position) of the inverse permutation in i (all permutations)

Using built-ins, 46 43 bytes

a[(a=Ordering)/@Permutations@Range@#][[#]]&

1-indexed.

Answer 3

05AB1E, 14 13 bytes

Very memory inefficient. Now even more memory inefficient (but 1 byte shorter).
0-based range.
Uses CP-1252 encoding.

ƒ¹ÝœD¹èNkˆ}¯k

Try it online! or as a Modified test suite

Explanation

ƒ               # for N in range[0 .. x]
 ¹ÝœD           # generate 2 copies of all permutations of range[0 .. x]
     ¹è         # get permutation at index x
       Nkˆ      # store index of N in that permutation in global list
         }      # end loop
          ¯k    # get index of global list (inverse) in list of permutations

Answer 4

MATL, 15 bytes

:Y@tGY)Z)G:=!Af

Input and output are 1-based.

Similar to @MartinEnder's CJam answer, but finds the inverse permutation by composing all possible permutations with that specified by the input, and seeing which has become the identity permutation.

It runs out of memory in the online compiler for input 10.

Try it online!

Explanation

:      % Implicitly input N. Push range [1 2 ... N]
Y@     % Matrix witll all permutations of size N. Each permutation is a row
tGY)   % Duplicate. Get the N-th row
Z)     % Use that as a column index into the matrix of all permutations
G:=    % Compare each row with [1 2 ... N]
!Af    % Find index of the row that matches. Implicitly display

Answer 5

Pyth, 12 bytes

xJ.phQxL@JQh

Test suite

0 indexed.

Explanation:

xJ.phQxL@JQh
xJ.phQxL@JQhQ    Implicit variable introduction
                 Q = eval(input())
  .phQ           Form all permutations of range(Q+1), namely [0, 1, .. Q]
 J               Save to J.
        @JQ      Take the Qth element of J.
      xL   hQ    Map all elements of [0, 1, ..., Q] to their index in above
x                Find the index in J of the above.

Answer 6

CJam, 16 bytes

ri_)e!_@=_$\f#a#

Indices are 0-based.

Try it online!

I doesn't get a lot more inefficient than this... runs out of memory with Java's default settings for inputs greater than 8 (but works in principle for arbitrary inputs given a sufficient number of universes of time and memory).

Explanation

ri    e# Read input and convert to integer N.
_)e!  e# Duplicate N, get all permutations of [0 1 ... N].
_@=   e# Duplicate permutations, get the Nth permutation.
_$    e# Duplicate and sort to get the sorted range [0 1 ... N].
\f#   e# For each of these values, get its index in the Nth permutation.
      e# This inverts the permutation.
a#    e# Find the index of this new permutation in the list of all permutations.

Answer 7

GAP, 108 bytes

h:=l->n->PositionProperty(l,p->l[n]*p=());
f:=n->h(Set(SymmetricGroup(First([1..n],k->Factorial(k)>=n))))(n);

1-indexed. Newlines not counted, they are not needed. I don't really have to assign the final function to a name, but ...

h is a curried function taking a list of permutations and an index into that list and returning the index of the inverse permuation. Without restrictions, I'd just do Position(l,l[n]^-1). f calls that function with the sorted permutations of a big enough symmetric group and the given n.

I could just write SymmetricGroup(n), then the function could be computed for values up to 9. Since there are already much smaller solutions, I prefer to be able to do this:

gap> f(100001);
303017

A really efficient 0-indexed solution that works for arguments below 99! (and can be made to work for arguments below 999! at the cost of one byte) is this one:

f:=function(n)
 local m,l,p,i,g;
 m:=First([1..99],k->Factorial(k)>n);
 g:=List([m-1,m-2..0],Factorial);
 l:=[1..m];
 p:=[];
 for i in g do
  Add(p,Remove(l,QuoInt(n,i)+1));
  n:=n mod i;
 od;
 return Sum(ListN(List([1..m],i->Number([1..Position(p,i)],j->p[j]>i)),g,\*));
end;

After deleting whitespace, this has 255 bytes.

Answer 8

Jelly, 14 13 9 bytes

-4 bytes thanks to @Dennis (which he golfed further using the quick ⁺ in his answer)

Œ!ịịŒ!$iR

Another very slow implementation.
1-based indexing employed here, so expected results are:

input:  1 2 3 4 5 6 7 8  9 10 11
output: 1 2 3 5 4 6 7 8 13 19  9

No point in even putting up an online IDE link, as TIO kills at an input of 10. Local results (last is very slow and required a tonne of memory!):

C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 1
1
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 2
2
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 3
3
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 4
5
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 5
4
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 6
6
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 7
7
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 8
8
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 9
13
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 10
19
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 11
9

How?

Œ!ịịŒ!$iR - Main link 1: n
      $   - last two links as a monad
    Œ!    -     permutations of implicit range [1,2,3,...,n]
   ị      -     value at index n (the nth permutation)
Œ!        - permutations of implicit range [1,2,3,...,n]
  ị       - value at index (the indexes of the permuted values in the nth permutation)
       i  - index of
        R - range [1,2,3,...,n]

Note: no need to sort the permutations as we are using the same ordering for both finding the permutation and and it's inverse.

Answer 9

JavaScript (ES6), 163 120 110 bytes

f=(n,a=[],i=0,r=0,[j,...b]=a)=>n?a.splice(n%-~i,0,i)|f(n/++i|0,a,i):i?f(n,b,i-1,b.reduce((r,k)=>r+=k>j,r*i)):r

<input type=number min=0 oninput=o.textContent=f(+this.value)><pre id=o>

0-indexed. Works by converting the index to a permutation, inverting it, then converting back to an index. Edit: Saved about 25% by making f invert and reverse the permutation, then making g convert the reversed permutation back to an index. Saved a further 10 bytes by combining the two recursive calls into a single function. Ungolfed:

function index(n) {
    var a = [0];
    for (var i = 1; n = Math.floor(n / i); i++) {
        var j = i - n % (i + 1);
        for (var k = 0; k < i; k++) {
            if (a[k] > j) a[k]++;
        }
        a.push(j);
    }
    a = [...a.keys()].map(k => a.indexOf(k));
    while (i) {
        n *= i--;
        j = a.pop();
        for (k = 0; k < i; k++) {
            if (a[k] > j) n++;
        }
    }
    return n;
}

Answer 10

J, 55 50 bytes

g=:/:~i.@#
[:(#\.#.+/@(<{.)\.)@g(-i.)@>:g@g@,/@#:]

Based on the J essay on Permutation Index.

This code only requires memory on the order of n but uses more time since it sorts the list n times and searches it n times for each index.

Using the builtin /: which is able to find the grade of a list and the inverse of a permutation, there is a 42 byte solution that is more efficient.

[:(#\.#.+/@(<{.)\.)@/:(-i.)@>:/:@/:@,/@#:]

This version only requires 44 seconds to compute the last test case when compared against the other which requires 105 seconds.

Usage

   g =: /:~i.@#
   f =: [:(#\.#.+/@(<{.)\.)@g(-i.)@>:g@g@,/@#:]
   (,.f"0) 0 1 2 3 4 5 6 13 42 100 1000 2000 10000
    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
   timex 'r =: f 100000'
105.787
   r
303016

Answer 11

Python 2, 130 129 bytes

p=lambda x,k,j=1:x[j:]and p(x,k/j,j+1)+[x.pop(k%j)]
n=input();r=range(n+2);k=0
while[p(r*1,n)[i]for i in p(r*1,k)]>r:k+=1
print k

Answer 12

Python 2, 116 114 bytes

from itertools import*
def f(n):r=range(n+1);l=list(permutations(r));print l.index(tuple(l[n].index(v)for v in r))

repl.it

0-based. Slow and memory hungry but short on bytes.

---

Using no permutation functions; both memory and time efficient. 289 285 bytes

-4 bytes thanks to @Christian Sievers (full permutation already formed)

h=lambda n,v=1,x=1:v and(n>=v and h(n,v*x,x+1)or(v,x-1))or n and h(n-1,0,n*x)or x
i=lambda p,j=0,r=0:j<len(p)and i(p,j+1,r+sum(k<p[j]for k in p[j+1:])*h(len(p)-j-1,0))or r
def f(n):t,x=h(n);g=range(x);o=g[:];r=[];exec"t/=x;x-=1;r+=[o.pop(n/t)];n%=t;"*x;return i([r.index(v)for v in g])

I know it's code golf but I think @Pietu1998 is interested in efficient implementations also.

See it in action at repl.it

While this uses more bytes than the reference implementation comparing for n=5000000:

ref:    6GB 148s  
this: 200KB <1ms

f is the reverse index function.

f first gets the next factorial above n, t, and the integer whose factorial that is, x by calling h(n), and sets g=range(x), the items that will make up the permutation, o=g[:], and the permutation holder, r=[]

Next it constructs the permutation at index n by poping the indexes of the factorial base representation of n in turn from the items, o, and appending them to r. The factorial base representation is found by div and mod of n with t where t is div'd by x and x decrements down to 1.

Finally it finds the index of the reverse permutation by calling i with the reverse permutation, [r.index(v)for v in g]

h is a dual-purpose function for either calculating a factorial of a non-negative integer or calculating both the next factorial above a non-negative integer and the integer that makes that factorial.

In it's default state v=1 and it does the latter by multiplying v by x (also initially 1) and incrementing x until n is at least as big, then it returns v and x-1 in a tuple.

To calculate n! one calls h(n,0) which multiples x (initially 1) by n and decrements n until n is 0 when it returns x.

i provides the lexicographical index of a permutation, p, of the items [0,1,...n] by adding up the products of the factorial of the factorial base of each index, h(len(p)-j-1,0), and how many items to the right of the index are less than the value at that index, sum(k<p[j]for k in p[j+1:]).

Answer 13

Actually, 18 11 bytes

This answer uses the algorithm in Dennis' Jelly answer but is 0-indexed. Golfing suggestions welcome! Try it online!

4╞r;)╨E╨♂#í

Ungolfing

      Implicit input n.
4╞    Push 4 duplicates of n. Stack: n, n, n, n
r;)   Push the range [0...n], and move a duplicate of that range to BOS for later.
╨E    Push the n-length permutations of [0...n] and get perm_list[n].
        Stack: perm_list[n], n, [0...n]
╨     Push the n-length permutations of perm_list[n].
♂#    Convert every "list" in the zip to an actual list.
        Stack: perm(perm_list[n]), [0...n]
í     Get the index of [0...n] in the list of permutations of perm_list[n].
      Implicit return.