Wprowadzenie

Permutacje leksykograficzne listy zawierającej n elementów mogą być ponumerowane od 0 do n ! - 1. Na przykład 3! = 6 permutacji (1,2,3)byłoby (1,2,3), (1,3,2), (2,1,3),(2,3,1) , (3,1,2), (3,2,1).

Po zastosowaniu permutacji do listy jej elementy są uporządkowane w tej samej kolejności, co liczby w permutacji. Na przykład zastosowanie permutacji (2,3,1)dol = (a,b,c) wydajności (l[2],l[3],l[1]) = (b,c,a).

Odwrotność permutacji jest definiowana jako permutacja, która odwraca tę operację, tj. Zastosowanie permutacji, a następnie jej odwrotność (lub odwrotnie) nie modyfikuje tablicy. Na przykład odwrotność (2,3,1)jest (3,1,2), ponieważ stosuje się to do (b,c,a)zbiorów (a,b,c).

Również odwrotność permutacji zastosowana do samej permutacji daje liczby całkowite 1… n . Na przykład zastosowanie (3,1,2)do (2,3,1)plonów (1,2,3).

Definiujemy teraz funkcję revind ( x ) jako indeks odwrotnej permutacji permutacji o indeksie x . (To jest A056019 , jeśli jesteś zainteresowany.)

Ponieważ permutacja z indeksem i modyfikuje tylko ostatnie k elementów listy iff 0 ≤ i < k !, Możemy dodać dowolną liczbę elementów na początku listy bez wpływu na revind ( i ). Dlatego długość listy nie wpływa na wynik.

Wyzwanie

Twoim zadaniem jest zaimplementowanie revind ( x ). Napiszemy pełny program lub funkcję, która przyjmuje jedną nieujemną liczbę całkowitą x jako dane wejściowe / argument i wyprowadza / zwraca wynik jako jedną nieujemną liczbę całkowitą.

Dane wejściowe i wyjściowe mogą być indeksowane 0 lub indeksowane 1, ale musi to być spójne między nimi.

Wbudowane, które generują permutacje według indeksu, zwracają indeks permutacji lub znajdują odwrotną permutację, są zakazane. (Wbudowane, które generują wszystkie permutacje lub następne permutacje są dozwolone.)

Standardowy golf zasady .

Przykłady

Poniższe przykłady są indeksowane według 0.

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

Implementacja referencyjna (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]

Galaretka , 6 bajtów

ịŒ!⁺iR

We / wy używa indeksowania 1. Bardzo wolny i głodny pamięci.

Weryfikacja

Dopóki dane wejściowe nie przekraczają 8! = 40320 , wystarczy wziąć pod uwagę wszystkie permutacje tablicy [1,…, 8] . W ostatnim przypadku testowym permutacje [1,…, 9] wystarczają .

Z nieco zmodyfikowanym kodem, który uwzględnia tylko permutacje pierwszych 8 lub 9 dodatnich liczb całkowitych, możesz wypróbować online! lub sprawdź wszystkie pozostałe przypadki testowe .

Jak to działa

ịŒ!⁺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.

Alternatywne podejście, 6 bajtów (nieprawidłowe)

Œ!Ụ€Ụi

Jest tak samo długi i wykorzystuje zakazany atom podwyższenia klasyỤ , ale jest (prawdopodobnie) bardziej idiomatyczny.

Przygotowując 8 (lub 9 dla ostatniego przypadku testowego), możemy faktycznie wypróbować online!

Jak to działa

Œ!Ụ€Ụ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.

Mathematica, 74 bajty

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

Wykorzystuje indeksowanie 1. Bardzo nieefektywne. (zużywa ~ 11 GB pamięci, gdy wejście jest11 )

Wyjaśnienie

j=Range@#

Wygeneruj listę od 1 do N. Przechowuj w j.

i=Permutations[...]

Znajdź wszystkie permutacje z j. Przechowuj to w i.

k=Position

Zapisz Positionfunkcję w k. (aby zmniejszyć liczbę bajtów przy Positionponownym użyciu )

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

Znajdź odwrotną permutację N-tej permutacji.

Max@k[i,...]

Znajdź k( Position) odwrotnej permutacji wi (wszystkie permutacje)

Korzystanie z wbudowanych 46 43 bajtów

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

1-indeksowany.

MATL , 15 bajtów

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

Wejścia i wyjścia są oparte na 1.

Podobne do odpowiedzi CJam @ MartinEnder , ale odnajduje odwrotną permutację, komponując wszystkie możliwe permutacje z określonymi przez dane wejściowe i sprawdzając, która stała się permutacją tożsamości.

W kompilatorze online zabrakło pamięci na dane wejściowe 10.

Wypróbuj online!

Wyjaśnienie

:      % 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

Pyth, 12 bajtów

xJ.phQxL@JQh

Zestaw testowy

0 zindeksowanych.

Wyjaśnienie:

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.

05AB1E , 14 13 bajtów

Bardzo nieefektywna pamięć. Teraz jeszcze bardziej nieefektywna pamięć (ale o 1 bajt krótsza).
Zakres 0.
Wykorzystuje kodowanie CP-1252 .

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

Wypróbuj online! lub jako zmodyfikowany pakiet testowy

Wyjaśnienie

ƒ               # 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

CJam , 16 bajtów

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

Indeksy są oparte na 0.

Wypróbuj online!

Nie wydaję się o wiele bardziej nieefektywny niż to ... brakuje pamięci przy domyślnych ustawieniach Javy dla danych wejściowych większych niż 8 (ale działa w zasadzie dla dowolnych danych wejściowych, biorąc pod uwagę wystarczającą liczbę wszechświatów czasu i pamięci).

Wyjaśnienie

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.

GAP , 108 bajtów

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

1-indeksowany. Nowe linie nie są liczone, nie są potrzebne. Tak naprawdę nie muszę przypisywać końcowej funkcji do nazwy, ale ...

hjest funkcją curry, która pobiera listę permutacji i indeks do tej listy i zwraca indeks odwrotnej permuacji. Po prostu bym to zrobił Position(l,l[n]^-1). fwywołuje tę funkcję z posortowanymi permutacjami odpowiednio dużej grupy symetrycznej i podanąn .

Mógłbym tylko napisać SymmetricGroup(n), a następnie funkcję można obliczyć dla wartości do 9. Ponieważ istnieją już znacznie mniejsze rozwiązania, wolę móc to zrobić:

gap> f(100001);
303017

Naprawdę skuteczne rozwiązanie z indeksowaniem 0, które działa dla argumentów poniżej 99! (i może sprawić, że będzie działał dla argumentów poniżej 999! kosztem jednego bajtu) jest następujący:

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;

Po usunięciu białych znaków ma 255 bajtów.

JavaScript (ES6), 163 120 110 bajtów

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-indeksowane. Działa poprzez konwersję indeksu na permutację, odwrócenie go, a następnie konwersję z powrotem do indeksu. Edycja: Zapisano około 25%, dokonując fodwrócenia i odwrócenia permutacji, a następnie gprzekształcając odwróconą permutację z powrotem w indeks. Zapisano kolejne 10 bajtów, łącząc dwa wywołania rekurencyjne w jedną funkcję. Nie golfowany:

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;
}

JOT, 55 50 bajtów

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

Na podstawie eseju dotyczącego indeksu permutacji .

Ten kod wymaga tylko pamięci w kolejności, nale zużywa więcej czasu, ponieważ sortuje listęn czasy i wyszukuje je ndla każdego indeksu.

Korzystając z wbudowanego narzędzia, /:które potrafi znaleźć ocenę listy i odwrotność permutacji, istnieje 42-bajtowe rozwiązanie, które jest bardziej wydajne.

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

Ta wersja wymaga tylko 44 sekund na obliczenie ostatniego przypadku testowego w porównaniu z drugim, który wymaga 105 sekund.

Stosowanie

   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

Galaretka , 14 13 9 bajtów

-4 bajty dzięki @Dennis (którą grałem dalej Korzystanie z szybkiego ⁺na jego odpowiedź )

Œ!ịịŒ!$iR

Kolejna bardzo powolna implementacja.
Zastosowano tutaj indeksowanie 1, więc oczekiwane wyniki to:

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

Nie ma sensu nawet umieszczać internetowego łącza IDE, ponieważ TIO zabija na wejściu 10. Wyniki lokalne (ostatnie jest bardzo wolne i wymaga tony pamięci!):

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

W jaki sposób?

Œ!ịịŒ!$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]

Uwaga: nie trzeba sortować permutacji, ponieważ używamy tej samej kolejności zarówno dla znalezienia permutacji, jak i odwrotnie.

Python 2, 116 114 bajtów

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

W oparciu o 0. Powolny i głodny pamięci, ale mało bajtów.

Bez użycia funkcji permutacji; oszczędność pamięci i czasu. 289 285 bajtów

-4 bajty dzięki @Christian Sievers (już utworzono pełną permutację)

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

Wiem, że to jest golf golfowy, ale myślę, że @ Pietu1998 jest również zainteresowany wydajnymi implementacjami.

Zobacz to w akcji na repl.it

Chociaż wykorzystuje to więcej bajtów niż implementacja referencyjna w porównaniu do n=5000000:

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

f jest funkcją wstecznego indeksu.

fPierwszy dostaje następny silnia powyżej n, toraz liczbę całkowitą, której silnia czyli xdzwoniąch(n) i zestawów g=range(x), elementy, które składają się na permutacji,o=g[:] i posiadacz permutacji,r=[]

Następnie konstruuje permutację przy indeksie n, popwprowadzając indeksy reprezentacji podstawy silni z nkolei z elementów oi dołączając je do r. Reprezentacja silnia podstawowa jest określana przez div i mod nz tgdzie tdiv jest przezx i xzmniejsza się do1 .

Wreszcie znajduje indeks odwrotnej permutacji, wywołując iodwrotną permutację,[r.index(v)for v in g]

h jest funkcją podwójnego zastosowania do obliczania silni nieujemnej liczby całkowitej lub do obliczania zarówno następnego silnia powyżej nieujemnej liczby całkowitej, jak i liczby całkowitej, która czyni tę silnię.

W stanie domyślnym v=1robi to drugie, mnożąc vprzez x(również początkowo 1) i zwiększając, xaż nbędzie co najmniej tak duży, a następnie zwraca vix-1 krotce.

Aby obliczyć n!jedno połączenie, h(n,0)które się zwielokrotniax (początkowo 1), których autorem jest ni zmniejsza naż njest 0, kiedy wraca x.

izapewnia indeks leksykograficzny permutacji pprzedmiotów[0,1,...n] poprzez dodanie produktów z silni silni podstawy każdego indeksu, h(len(p)-j-1,0)i jak wiele elementów po prawej stronie wskaźnika jest mniejsza niż wartość w tym indeksie sum(k<p[j]for k in p[j+1:]).

Python 2, 130 129 bajtów

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

Faktycznie , 18 11 bajtów

Ta odpowiedź korzysta z algorytmu zawartego w odpowiedzi Dennisa „Jelly”, ale ma indeks 0. Zapraszamy do gry w golfa! Wypróbuj 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.