Фон

Соотношение перестановок , как определено в Википедии , выглядит следующим образом:

Знак или сигнатура перестановки σ обозначается как sgn (σ) и определяется как +1, если σ четное, и -1, если σ нечетное.

Знак перестановки может быть явно выражен как

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

где N (σ) - число инверсий в σ.

Альтернативно, знак перестановки σ может быть определен из ее разложения в произведение транспозиций как

sgn (σ) = (−1) ^ m

где m - количество транспозиций в разложении.

Для тех из вас, кто не любит греческий алфавит в своей математике, я постараюсь немного упростить определение на примере (также украденном из википедии).

пример

Рассмотрим входной массив {1, 2, 3, 4, 5}и перестановку его, скажем, {3, 4, 5, 2, 1}. Чтобы перейти от исходного массива к его перестановке, вы должны поменять местами индексы 0и 2, 1и 3, затем 2и4 . Хотя это не единственное решение, четность четко определена, так что это работает для всех случаев.

Поскольку это требует 3 перестановок, мы помечаем эту перестановку oddчетностью. Как и следовало ожидать, говорят, что перестановка, которая требует четного количества перестановок, имеетeven четность.

Вызов

Ваша задача состоит в том, чтобы написать программу как можно меньше байтов, чтобы определить четность перестановки. Ваша программа или функция должна:

• Примите в качестве аргументов два входных массива (или строки), представляющих набор до и после перестановки.
• Вернуть или напечатать символ eдля четного или oнечетного, учитывая перестановку.
• Следует предположить, что все индексы в массивах или строках имеют уникальные значения.

Тестовые случаи

Предполагая, что вы объявили функцию с именем f:

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

Это код-гольф , выигрывает самая короткая программа в байтах!

Желе, 13 12 байт

żṗ2</€⁺Sị“oe

Попробуйте онлайн!

Как это устроено

żṗ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 байт

1 байт удален благодаря предложению Денниса

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

Это работает в текущей версии (15.0.0) языка.

Попробуйте онлайн !

объяснение

Здесь используется определение паритета в терминах инверсий. Инверсия - это пара элементов во втором массиве, которые расположены в «неправильном» порядке по сравнению с первым массивом. Поскольку первый массив не нужно сортировать, мы сначала сортируем его, и та же самая перестановка, необходимая для этой сортировки, применяется ко второму массиву. Тогда инверсия соответствует паре элементов, которая не увеличивается во втором массиве.

Также обратите внимание, что два входных массива можно поменять местами, и результат будет одинаковым. Поэтому не важно, какой массив считается «оригинальным», а какой «переставленным».

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 

Октава, 56 52 байта

Кажется, что пока никто не использует этот подход: в основном я просто использую определители соответствующих матриц перестановок. Выражение det(eye(nnz(a))(a,:))возвращает определитель матрицы перестановок, определенной вектором a. Тогда это просто вопрос извлечения правильного символа из строки, в зависимости от результата.

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

Haskell, 58 байт

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

Использование:

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

Тот же метод, что и мой ответ на Python . гордый haskeller сохранил байт с cycle.

Python 2, 68 байт

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

Использование:

>>> 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'

Подсчитывает количество пар инверсии двух сжатых списков, т.е. значения (a,A)и (b,B)из каждого списка в том же индексе с a<bи A>B. Эти сравнения объединяются a<b<M>A>B, используя свойство того, что список Mбольше любого числа. Затем сумма берется по модулю 2 и превращается в eили o.

JavaScript (ES6), 73 байта

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

Поскольку нас интересует только паритет, любые повторяющиеся транспозиции просто отменяются. Удобно, чтобы индексы массивов JavaScript не были многомерными.

Mathematica, 77 байтов

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

Я согласен!

Mathematica, 31 байт

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

Подпись [список] дает подпись перестановки, необходимой для размещения элементов списка в каноническом порядке

Мы можем переупорядочить один список в другой, сначала переупорядочив один список в любой порядок (в данном случае канонический порядок) и переупорядочив этот список в окончательный список. Знак общей перестановки является четным, если знаки двух подстановок равны.