Odwrotny wskaźnik permutacji

17

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 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]
PurkkaKoodari
źródło
1
Musiałem przyjrzeć się definicji odwrotnej permutacji, aby zrozumieć to wyzwanie. Uważam twój przykład za (a,b,c)wyjątkowo niejasny. Proszę załączyć właściwe wyjaśnienie, czym jest odwrotna permutacja.
Fatalize
@Fatalize To trochę trudno wyjaśnić po prostu. Lepiej teraz?
PurkkaKoodari
Galaretka ma atom (stopień w górę), który sortuje indeksy tablicy według odpowiadających im wartości. To dzieje się odwrócić permutacji 1, ..., n , ale to nie działa dla innych permutacji. Czy zabronione jest wbudowane?
Dennis,
@Dennis Trudne pytanie. Technicznie znajduje odwrotność dowolnej permutacji po zastosowaniu jej do ściśle rosnącej listy. Dlatego powiem, że nie wolno. (Jeśli ktoś zdecydowanie się nie zgadza, nie
wahaj

Odpowiedzi:

5

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.
Dennis
źródło
6

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.

JungHwan Min
źródło
2
„Wbudowane, które ... znajdują odwrotną permutację są zakazane”
Greg Martin,
@GregMartin, ah, jakoś tęskniłem za tą częścią i widziałem tylko część „zwróć indeks permutacji”. Silly ja ... Nowy kod nie ma tego problemu.
JungHwan Min
tak, zgadzam się, że łatwo było przegapić. 74 bajty - wciąż imponujące!
Greg Martin
5

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
Luis Mendo
źródło
5

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.
isaacg
źródło
5

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
Emigna
źródło
4

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.
Martin Ender
źródło
3

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.

Christian Sievers
źródło
Dobra robota! Miałem nadzieję, że uda mi się też znaleźć wydajne rozwiązania.
PurkkaKoodari,
3

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;
}
Neil
źródło
1
@JonathanAllan Przepraszamy, myślałem, że zauważyłem 9-bajtowe oszczędności w ostatniej chwili, ale nie udało mi się go dokładnie przetestować. Wróciłem do poprzedniej wersji.
Neil,
Bardzo eleganckie wdrożenie teraz.
Jonathan Allan
1
@JonathanAllan Okazuje się, że jest jeszcze bardziej szykowny, jeśli odwrócę fpermutację zamiast g...
Neil,
3

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
mile
źródło
+1 za wydajność pamięci, której języki gry w golfa nie mogą dotknąć.
Magic Octopus Urn
2

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.

Jonathan Allan
źródło
Nie możesz go przetestować z mojego telefonu, ale czy nie możesz pozbyć się linku 2 i zrobić głównego ÇịịÇ$iR?
Dennis
Właściwie to Rwcześniej Œ!jest niejawne, więc Œ!ịịŒ!$iRpowinno wykonać zadanie.
Dennis
Tak, to był bardzo pośpieszny wpis przed spotkaniem z przyjaciółmi.
Jonathan Allan,
2

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, xnbę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 nnjest 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:]).

Jonathan Allan
źródło
Myślę, że przy konstruowaniu permutacji nie musisz specjalnie traktować ostatniego przypadku. Nie miałem w swoim 255-bajtowym rozwiązaniu GAP.
Christian Sievers,
Na końcu dodaję go osobno, ponieważ w przeciwnym razie wystąpiłby błąd dzielenia przez zero t/=x.
Jonathan Allan
Zajęło mi trochę czasu, aby zobaczyć: pętla już to wszystko, można zastąpić (r+o)przez r.
Christian Sievers,
Masz rację! Dziękuję bardzo.
Jonathan Allan,
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
Dennis
źródło
1

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.
Sherlock9
źródło