Permutacja rozmiaru n to zmiana kolejności pierwszych n dodatnich liczb całkowitych. (co oznacza, że ​​każda liczba całkowita pojawia się raz i dokładnie raz). Permutacje można traktować jak funkcje, które zmieniają kolejność listy elementów o rozmiarze n . Na przykład

(4 1 2 3) ["a", "b", "c", "d"] = ["d", "a", "b", "c"]

W ten sposób permutacje można składać jak funkcje.

(4 1 2 3)(2 1 3 4) = (4 2 1 3)

Daje to wiele interesujących właściwości. Dziś koncentrujemy się na odrodzeniu . Permutacje y i x (oba o rozmiarze n ) są koniugatami iff istnieją permutacje g i g ^-1 (również o rozmiarze n ), takie że

x = gyg-1

a gg ^-1 jest równe permutacji tożsamości (pierwsze n liczb we właściwej kolejności).

Twoim zadaniem jest wziąć dwie permutacje tego samego rozmiaru za pomocą standardowych metod wprowadzania i zdecydować, czy są one sprzężone. Powinieneś wypisać jedną z dwóch spójnych wartości, jedną, jeśli są one sprzężone, a drugą, jeśli nie są.

To jest golf golfowy, więc odpowiedzi będą liczone w bajtach, przy czym mniej bajtów będzie lepszych.

Istnieje wiele twierdzeń na temat permutacji sprzężonych, które są do Państwa dyspozycji, więc powodzenia i szczęśliwego grania w golfa.

Możesz wziąć dane wejściowe jako uporządkowany kontener wartości (1-n lub 0-n) reprezentujący permutację jak powyżej lub jako funkcję, która bierze uporządkowany kontener i wykonuje permutację. Jeśli wybierzesz funkcję, powinieneś wziąć ją jako argument, a nie mieć jej z góry określoną nazwę.

Przypadki testowe

(1) (1) -> True
(1 2) (2 1) -> False
(2 1) (2 1) -> True
(4 1 3 2) (4 2 1 3) -> True
(3 2 1 4) (4 3 2 1) -> False 
(2 1 3 4 5 7 6) (1 3 2 5 4 6 7) -> True

Python 2 , 87 bajtów

f=lambda P,k:k<1or len({sum([x==eval('L['*k+'x'+']'*k)for x in L])for L in P})&f(P,k-1)

Wypróbuj online!

Pobiera dane wejściowe Pjako parę obu permutacji i kich długości. Wyjścia 1dla koniugatów i 0nie.

Wykorzystuje to wynik:

Dwie permutacje x i y są sprzężone dokładnie, jeśli ich k -te potęgi x ^k i y ^k mają równą liczbę stałych punktów dla każdego k od 0 do n .

Dwie permutacje sprzężone spełniają to, ponieważ ich k- te moce również są sprzężone, a sprzężenie zachowuje liczbę stałych punktów.

Mniej oczywiste jest, że dowolne dwie niesprzężone kombinacje zawsze się różnią. W szczególności koniugacja jest określona przez posortowaną listę długości cykli, które można odzyskać z liczby punktów stałych. Jednym ze sposobów na wykazanie tego jest algebra liniowa, choć może to być przesada.

Niech X będzie macierzą permutacji dla x . Następnie liczba stałych punktów x ^k wynosi Tr (X ^k ) . Te ślady to suma mocy symetryczne wielomiany o wartości własnych X ^k z wielości. Te wielomiany dla k od 0 do n pozwalają odzyskać odpowiednie elementarne symetryczne wielomiany tych wartości własnych, a zatem charakterystyczny wielomian, a więc same wartości własne.

Ponieważ te wartości własne są pierwiastkami jedności odpowiadającymi cyklom x , z nich możemy odzyskać rozmiary cykli i ich wielokrotności. Zatem nasz „podpis” identyfikuje permutację aż do koniugacji.

J , 25 bajtów 23 bajty 16 bajtów

milczące rozwiązanie mil :

-:&([:/:~#&>)&C.

Wyraźne rozwiązanie PO:

c=:4 :'-://:~"1#&>C.&>x;y'   

To sprawdza, czy permutacje xiy mają ten sam typ cyklu, przy użyciu wbudowanej C.funkcji do tworzenia reprezentacji cyklu.

   4 1 3 2   c   4 2 1 3
1
   3 2 1 4   c   4 3 2 1
0
   2 1 3 4 5 7 6   c   1 3 2 5 4 6 7
1

MATL , 20 19 17 16 bajtów

xY@!"&G@)@b)X=va

Dane wejściowe: dwa wektory kolumnowe (wykorzystujące ;jako separator). Wyjście: 1jeśli koniugat, 0jeśli nie.

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

Żadnych twierdzeń o permutacjach (z czystej ignorancji); po prostu brutalna siła i te dwa fakty:

• Dla dwóch permutacji p i q skład pq jest równoważny z użyciem p do zindeksowania elementów q .

• Warunek x = gyg- ¹ jest równoważny xg = gy .

Skomentowany kod:

x      % Implicitly input first permutation, x. Delete it. Gets copied into clipboard G
Y@     % Implicitly input second permutation, y. Push a matrix with all permutations
       % of its elements, each permutation on a different row. So each matrix row is
       % a permutation of [1 2 ...n], where n is the size of y
!      % Transpose. Now each permutation is a column
"      % For each column
  &G   %   Push x, then y
  @    %   Push current column. This is a candidate g permutation
  )    %   Reference indexing. This gives g composed with y
  @    %   Push current column again
  b    %   Bubble up. Moves x to the top of the stack
  )    %   Reference indexing. This gives x composed with g
  X=   %   Are they equal as vectors? Gives true or false
  v    %   Concatenate stack so far. The stack contains the latest true/false result
       %   and possibly the accumulated result from previous iterations
  a    %   Any: gives true if any element is true. This is the "accumulating" function
       % Implicit end. Implicit display

Wolfram Language (Mathematica) , 44 bajty

Equal@@(PermutationCycles[#,Sort[0#]&]&/@#)&

Wypróbuj online!

Wolfram Language (Mathematica) , 44 bajty

x_±y_:=Or@@(#[[x]]==y[[#]]&/@Permutations@x)

Korzystanie z kodowania CP-1252, gdzie ±jest jeden bajt.

Wypróbuj online!

Galaretka , 11 bajtów

Œ!©Ụ€ịị"®⁸e

Wypróbuj online!

Jak to działa

Œ!©Ụ€ịị"®⁸e  Main link. Left argument: x. Right argument: y

Œ!©          Take all permutations g of x. Copy the result to the register.
   Ụ€        Grade up each; sort the indices of each permutation g by their
             corresponding values. For permutations of [1, ..., n], grading up
             essentially computes the inverse, g⁻¹.
     ị       Let each g⁻¹ index into y, computing g⁻¹y.
      ị"®    Let the results index into the corresponding g, computing g⁻¹yg.
         ⁸e  Test if x occurs in the result.

Łuska , 9 bajtów

¤¦ṠmöLU¡!

Zwraca 1dla koniugatu i 0dla niesprzężonego. Wypróbuj online!

Wyjaśnienie

Klasa sprzężoności permutacji P o L = [1,2, .., n] jest ustalana przez MultiSet zawierającej najmniej okres każdy numer L pod P . Gdy P jest wykonane w formie listy, mogę wymienić L z P i uzyskać ten sam MultiSet. Program oblicza odpowiedni multiset dla każdego wejścia i sprawdza, czy jeden jest sub-multiset drugiego. Ponieważ mają tę samą liczbę elementów, jest to równoważne z byciem tym samym multiset.

¤¦ṠmöLU¡!  Implicit inputs: two lists of integers.
¤          Apply one function to both and combine with another function.
  ṠmöLU¡!  First function. Argument: a list P.
  Ṡm       Map this function over P:
       ¡!  iterate indexing into P,
      U    take longest prefix with unique elements,
    öL     take its length.
 ¦         Combining function: is the first list a subset of the other, counting multiplicities?

Perl, 61 58 57 bajtów

Obejmuje +2dlaap

Daj permutacje oparte na 0 jako 2 linie na STDIN

perl -ap '$_=[@1]~~[@1=map{-grep$_-$G[$i++%@G],@F=@G[@F]}@G=@F,0]'
3 0 2 1
3 1 0 2
^D

Algorytm jest niewielką odmianą tej w rozwiązaniu xnor

Ta starsza wersja kodu uderza błąd perla i zrzuca rdzeń dla kilku danych wejściowych mojego najnowszego perla 5.26.1, ale działa na starszym perlu 5.16.3.

@{$.}=map{-grep$_==$F[$i++%@F],@G=@F[@G]}@G=@F,0}{$_=@1~~@2

Jest to prawdopodobnie kolejny przykład mojego starego wroga perlgolfa, fakt, że perl nie przelicza prawidłowo swojego stacka.

JavaScript (ES6), 66 64 bajtów

(a,b,g=a=>b+a.map(h=(e,i)=>e-i&&1+h(a[e],i)).sort())=>g(a)==g(b)

Jeśli poprawnie odczytałem inne odpowiedzi, problem jest równoważny zliczaniu okresów wszystkich elementów i sprawdzaniu, czy dwie listy mają tę samą liczbę każdego okresu. Edycja: Zapisano 1 bajt dzięki @Arnauld, obliczając jeden mniej niż okres. Oszczędność kolejnego bajtu dzięki @Arnauld poprzez nadużywanie dziwnych reguł przymusu JavaScript do porównywania tablic. Kolejny bajt można uratować dzięki curry, ale nie lubię curry, chyba że jest to kurczak tikka masala.