Sprzężone permutacje

17

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
code-golf decision-problem combinatorics permutations abstract-algebra Post Rock Garf Hunter
źródło
Czy możemy brać dane wejściowe jako funkcję? Czy możemy również przyjąć rozmiar n?
xnor
@ xnor Pewnie w obu przypadkach. Nie jestem jednak pewien, jak pierwsze ci pomogą.
Post Rock Garf Hunter
Domyślne reguły wprowadzania funkcji pozwalają na założenie, że funkcja jest predefiniowana, co oszczędza bajty podczas zapisywania jej jako argumentu, jeśli na to pozwalasz.
xnor
@xnor Czy mówimy o tej zasadzie? Dotyczy to funkcji czarnej skrzynki, których nie są permutacje. Ma to sens, ponieważ konsensus ma na celu umożliwienie konkurowania języków bez wskaźników funkcji / obiektów, podczas gdy tutaj mogą, ponieważ permutacje mogą być reprezentowane inaczej.
Post Rock Garf Hunter
Byłem, nie myślałem o tym, żeby odróżnić ich od czarnej skrzynki. Więc tutaj dane wejściowe mogą być funkcją, ale tylko jako jawny argument?
xnor

Odpowiedzi:

6

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.

xnor
źródło
6

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
Mathias Dolidon
źródło
1
Witamy w PPCG i miły pierwszy post. Skróciłem twoją metodę do 16 bajtów -:&([:/:~#&>)&C.za pomocą milczącego formularza. Oto link TIO, aby go wypróbować.
mile
Dziękuję Ci. :) Wciąż jestem całkiem początkującym językiem J i chociaż wydaje mi się, że łatwo go dobrze wykorzystać z wyraźnymi formularzami, tworzenie skutecznych, cichych formularzy wciąż wymaga ode mnie nadmiernej refleksji. Dodam twoje rozwiązanie.
Mathias Dolidon
PS: czy nie liczymy również znaków przypisań funkcji? c=:
Mathias Dolidon
1
@MathiasDolidon Nie, domyślnie konsensus, nie liczymy znaków wymaganych do przypisania, ponieważ funkcja może być użyta w obecnej postaci (z nawiasami, ale ich nie liczymy).
Erik the Outgolfer
1
DOBRZE ! Zaktualizowałem z mocą wsteczną liczbę jawnych rozwiązań w tytule, aby to uwzględnić.
Mathias Dolidon
4

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

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.
Dennis
źródło
O ile rozumiem, tak naprawdę yindeksuje się do każdego g⁻¹, a nie na odwrót. Zobacz przykład (4 1 2 3)(2 1 3 4) = (4 2 1 3). Z twoim podejściem wynikałoby to (1 4 2 3)zamiast tego, ponieważ druga indeksuje się do pierwszej. Biorąc to pod uwagę, mam 12-bajtowe rozwiązanie, którego jeszcze nie zepsuje. :-)
Erik the Outgolfer
@EriktheOutgolfer Naprawiono.
Dennis
@Dennis Ale nie doszedłem do tego wniosku w oparciu o wyjaśnienie, doszedłem do dokładnie tego samego podejścia, z tym wyjątkiem, że miałem coś takiego Œ!©Ụ€⁹ịЀ®ị"⁸e(w zasadzie wszystkie indeksowanie z odwrotnymi argumentami), z wyjątkiem krótszych po dokonaniu poważnych modyfikacji. Nie sądzę, że g⁻¹ygjest taki sam jak gyg⁻¹. Myślę też, że twoja odpowiedź może skorzystać z tych modyfikacji, ale, jak powiedziałem wcześniej, nie chcę jeszcze zepsuć zabawy.
Erik the Outgolfer
Tak, jest dokładnie tak samo. Jeśli x = g⁻¹yg, po czym gxg⁻¹ = y, tak xi ysą koniugaty.
Dennis
Hm, mam wrażenie, że powinienem ujawnić moje 12-bajtowe rozwiązanie:eŒ!ị"Ụị@¥€¥¥
Erik the Outgolfer
1

Ł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?
Zgarb
źródło
1

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.

Ton Hospel
źródło
1

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.

Neil
źródło