17
\$\begingroup\$

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 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]
\$\endgroup\$
  • 12
    \$\begingroup\$ The scatter plot looks quite funny. :) \$\endgroup\$ – Martin Ender Oct 10 '16 at 18:34
  • 1
    \$\begingroup\$ I had to look up the definition of inverse permutation to understand this challenge. I find your example with (a,b,c) extremely unclear. Please include a proper explanation of what an inverse permutation is. \$\endgroup\$ – Fatalize Oct 11 '16 at 6:59
  • \$\begingroup\$ @Fatalize This is kinda hard to explain simply. Better now? \$\endgroup\$ – PurkkaKoodari Oct 11 '16 at 7:25
  • \$\begingroup\$ Jelly has the atom (grade up) which sorts the indices of an array by their corresponding values. This happens to invert a permutation of 1, …, n, but it doesn't work for other permutations. Is a forbidden built-in? \$\endgroup\$ – Dennis Oct 11 '16 at 14:53
  • \$\begingroup\$ @Dennis Hard question. Technically, it finds the inverse of any permutation after it's been applied to any strictly increasing list. Therefore I'm going to say not allowed. (If someone strictly disagrees, feel free to comment. I may change this if the community so desires.) \$\endgroup\$ – PurkkaKoodari Oct 11 '16 at 15:08

13 Answers 13

5
\$\begingroup\$

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.
\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ "Builtins that ... find the inverse permutation are banned" \$\endgroup\$ – Greg Martin Oct 11 '16 at 2:05
  • \$\begingroup\$ @GregMartin, ah, I somehow missed that part and only saw the "return the index of a permutation" part. Silly me... The new code doesn't have that issue. \$\endgroup\$ – JungHwan Min Oct 11 '16 at 4:27
  • \$\begingroup\$ yep, I agree it was easy to miss. 74 bytes—still pretty impressive! \$\endgroup\$ – Greg Martin Oct 11 '16 at 6:14
5
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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.
\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Nice work! I hoped to get some efficient solutions too. \$\endgroup\$ – PurkkaKoodari Oct 11 '16 at 8:45
3
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ @JonathanAllan Sorry, I thought I'd spotted a last-second 9-byte saving but I failed to test it thoroughly. I've reverted back to my previous version. \$\endgroup\$ – Neil Oct 11 '16 at 23:51
  • \$\begingroup\$ Very swish implementation now. \$\endgroup\$ – Jonathan Allan Oct 11 '16 at 23:55
  • 1
    \$\begingroup\$ @JonathanAllan Turns out to be even more swish if I get f to invert the permutation instead of g... \$\endgroup\$ – Neil Oct 12 '16 at 0:28
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ +1 for memory efficiency that golfing languages can't touch. \$\endgroup\$ – Magic Octopus Urn Oct 12 '16 at 16:27
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Can't test it from my phone, but couldn't you get rid of link 2 and make the main one ÇịịÇ$iR? \$\endgroup\$ – Dennis Oct 11 '16 at 13:54
  • \$\begingroup\$ Actually, the R before Œ! is implicit, so Œ!ịịŒ!$iR should do the job. \$\endgroup\$ – Dennis Oct 11 '16 at 13:58
  • \$\begingroup\$ Yeah, this was a very rushed entry before meeting friends. \$\endgroup\$ – Jonathan Allan Oct 11 '16 at 16:43
2
\$\begingroup\$

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:]).

\$\endgroup\$
  • \$\begingroup\$ I think you don't need to special case the last item when constructing the permutation. I didn't in my 255 byte GAP solution. \$\endgroup\$ – Christian Sievers Oct 11 '16 at 23:05
  • \$\begingroup\$ I add it separately at the end because otherwise there would be a divide by zero error when it does t/=x. \$\endgroup\$ – Jonathan Allan Oct 11 '16 at 23:09
  • \$\begingroup\$ Took me a while to see: the loop already does it all, you can replace (r+o) by r. \$\endgroup\$ – Christian Sievers Oct 11 '16 at 23:35
  • \$\begingroup\$ Uh, you are right! Thank you so much. \$\endgroup\$ – Jonathan Allan Oct 11 '16 at 23:49
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.