tło

Parzystości permutacji , jak określono Wikipedia , jest następujący:

Znak lub podpis permutacji σ jest oznaczony sgn (σ) i zdefiniowany jako +1, jeśli σ jest parzyste, a -1, jeśli σ jest nieparzyste.

Znak permutacji można jawnie wyrazić jako

sgn (σ) = (−1) ^ N (σ)

gdzie N (σ) to liczba inwersji w σ.

Alternatywnie znak permutacji σ można zdefiniować od jego rozkładu do iloczynu transpozycji jako

sgn (σ) = (−1) ^ m

gdzie m jest liczbą transpozycji w rozkładzie.

Dla tych z was, którzy nie lubią zupy greckiego alfabetu w swojej matematyce, postaram się nieco uprościć definicję na przykładzie (również skradzionym z wikipedii).

Przykład

Rozważmy układ wejściowy {1, 2, 3, 4, 5}i permutacji nim, powiedzmy {3, 4, 5, 2, 1}. Aby przejść z oryginalnej tablicy do jej permutacji, musisz zamienić indeksy 0oraz 2, 1a 3następnie 2i 4. Chociaż nie jest to unikalne rozwiązanie, parzystość jest dobrze zdefiniowana, więc działa to we wszystkich przypadkach.

Ponieważ wymaga 3 zamian, oznaczamy tę permutację oddparzystością. Jak można się spodziewać, mówi się, że permutacja wymagająca parzystej liczby zamian ma evenparzystość.

Wyzwanie

Wyzwaniem jest napisanie programu w jak najmniejszej liczbie bajtów, aby określić parzystość permutacji. Twój program lub funkcja musi:

• Zaakceptuj jako argumenty dwie tablice wejściowe (lub łańcuchy) reprezentujące zestaw przed i po permutacji.
• Zwróć lub wydrukuj znak eparzysty lub onieparzysty, biorąc pod uwagę permutację.
• Należy założyć, że wszystkie indeksy w tablicach lub ciągach mają unikalne wartości.

Przypadki testowe

Zakładając, że zadeklarowałeś funkcję o nazwie f:

f([10], [10]) == "e"
f([10, 30, 20], [30, 20, 10]) == "e"
f([10, 30, 20, 40], [30, 20, 40, 10]) == "o"

To jest golf golfowy , wygrywa najkrótszy program w bajtach!

Galaretka, 13 12 bajtów

żṗ2</€⁺Sị“oe

Wypróbuj online!

Jak to działa

żṗ2</€⁺Sị“oe  Main link. Arguments: A, B (lists)

ż             Zip A with B. Yields an array of pairs [x, σ(x)].
 ṗ2           Generate all pairs [[x, σ(x)], [y, σ(y)]].
   </€        Reduce each pair by </€.
              This maps [[x, σ(x)], [y, σ(y)]] to [x < y, σ(x) < σ(y)].
      ⁺       Repeat the previous link, i.e., execute </€ once more.
              This maps [x < y, σ(x) < σ(y)] to ((x < y) < (σ(x) < σ(y))), which is
              true if and only if x > y and σ(x) < σ(y).
       S      Sum. This counts the number of inversions.
        ị“oe  Retrieve the letter at the corresponding index.
              Indexing is 1-based and modular, so an odd sum retrieves the first
              letter, an even sum the second.

MATL , 17 16 bajtów

Usunięto 1 bajt dzięki sugestii Dennisa

2$St!<Rz2\'oe'w)

Działa to w bieżącej wersji (15.0.0) języka.

Wypróbuj online !

Wyjaśnienie

Wykorzystuje to definicję parzystości w kategoriach inwersji. Inwersja to para elementów w drugiej tablicy, które są w „złej” kolejności w porównaniu z pierwszą tablicą. Ponieważ pierwsza tablica nie musi być sortowana, najpierw ją sortujemy, a ta sama zmiana kolejności potrzebna do tego sortowania jest stosowana do drugiej tablicy. Wtedy inwersja odpowiada parze elementów, która nie rośnie w drugiej tablicy.

Należy również zauważyć, że dwie tablice wejściowe można zamieniać, a wynik jest taki sam. Dlatego nie jest ważne, która tablica jest uważana za „oryginalną”, a która „permutowaną”.

2$S     % implicitly take two row vectors. Sort second and apply the indices
        % of that sorting to the first
t!      % duplicate. Transpose into column vector
<       % true for elements of the column vector that exceed those of the 
        % row vector. Gives a 2D array with all pairs of comparisons
R       % keep only upper triangular part of that array
z       % number of nonzero elements. This is the number of inversions
2\      % parity of that number: gives 0 or 1
'oe'w   % push string 'eo' below the top of the stack
)       % apply index to produce 'e' or 'o'. An index 1 refers to the first
        % element, whereas 0 refers to the last. Implicitly display 

Oktawa, 56 52 bajtów

Wygląda na to, że jak dotąd nikt nie stosuje tego podejścia: w zasadzie używam tylko wyznaczników odpowiednich macierzy permutacji. Wyrażenie det(eye(nnz(a))(a,:))zwraca wyznacznik macierzy permutacji zdefiniowanej przez wektor a. Następnie jest tylko kwestia wyodrębnienia odpowiedniego znaku z łańcucha, w zależności od wyniku.

p=@(v)eye(nnz(v))(v,:);@(a,b)'ole'(det(p(a)*p(b))+2)

Haskell, 58 bajtów

k%l|m<-zip k l=cycle"eo"!!sum[1|(a,b)<-m,(c,d)<-m,a<c,b>d]

Stosowanie:

*Main> [8,3,5]%[5,3,8]
'o'

Ta sama metoda, co moja odpowiedź w języku Python . dumny haskeller uratował bajt cycle.

Python 2, 68 bajtów

lambda*M:"eo"[sum(a<b<M>A>B for a,A in zip(*M)for b,B in zip(*M))%2]

Stosowanie:

>>> f=lambda*M:"eo"[sum(a<b<M>A>B for a,A in zip(*M)for b,B in zip(*M))%2]
>>> f([8,3,5],[5,3,8])
'o'

Liczy liczbę par inwersji dwóch spakowanych list, tj. wartości (a,A)i (b,B)z każdej listy pod tym samym indeksem przy pomocy a<bi A>B. Te porównania są łączone jako a<b<M>A>B, przy użyciu właściwości, że lista Mjest większa niż dowolna liczba. Następnie suma jest pobierana modulo 2 i przekształcana w elub o.

JavaScript (ES6), 73 bajty

(a,b)=>"eo"[r=0,g=a=>a.map((e,i)=>a.slice(i).map(d=>r^=d<e)),g(a),g(b),r]

Ponieważ interesuje nas tylko parzystość, wszelkie zduplikowane transpozycje po prostu anulują. Dogodnie indeksy tablic JavaScript nie są wielowymiarowe.

Mathematica, 77 bajtów

If[Mod[Plus@@Length/@(Join[{0},#]&)/@PermutationCycles[#][[1]],2]==0,"e","o"]&

Zgadzam się!

Mathematica, 31 bajtów

If[Tr[Signature/@{##}]==0,o,e]&

Podpis [lista] podaje podpis permutacji potrzebny do umieszczenia elementów listy w porządku kanonicznym

Możemy zmienić kolejność jednej listy na drugą, najpierw zmieniając kolejność jednej listy na dowolną kolejność (w tym przypadku kolejność kanoniczną) i ponownie uporządkuj tę listę do ostatecznej listy. Znak całkowitej permutacji jest parzysty, jeśli znaki dwóch permutacji są równe.