ЗАДАНИЕ

ОПРЕДЕЛЕНИЯ

Рассмотрим точки {1,2,3,4,5} и все их перестановки. Мы можем найти общее количество возможных перестановок этих 5 точек с помощью простого трюка: визуализация, заполняющая 5 слотов этими точками, у первого слота будет 5 возможных чисел, у второго 4 (так как один использовался для заполнения первого слота) третий 3 и тд. Таким образом, общее количество перестановок составляет 5 * 4 * 3 * 2 * 1; это было бы 5! перестановки или 120 перестановок. Мы можем думать об этом как о симметричной группе S5, и тогда симметрическая группа Sn будет иметь n! or (n*n-1*n-2...*1)перестановки.

«Четная» перестановка - это та, где существует четное число циклов четной длины. Это легче понять , когда написано в циклической записи, например , (1 2 3)(4 5)переставляет 1->2->3->1и 4->5->4и имеет один 3 длину цикла (1 2 3)и один цикл длиной 2 (4 5). При классификации перестановки как нечетной или четной мы игнорируем циклы нечетной длины и говорим, что эта перестановка [ (1 2 3)(4 5)] является нечетной, так как имеет нечетное число {1} циклов четной длины. Ещё примеры:

1. (1)(2 3)(4 5)= два 2 цикла длины | ДАЖЕ |
2. (1 2 3 4 5)= нет четных циклов длины | ДАЖЕ | * обратите внимание, что если нет четных циклов длины, то перестановка четная.

Странные примеры:

1. (1 2)(3 4 5)= один цикл 2 длины | ODD |
2. (1)(2 3 4 5)= один цикл 4 длины | ODD |

Поскольку ровно половина перестановок в любой симметрической группе является четной, мы можем назвать четную группу чередующейся группой N, так что S5 = 120 A5 = 60 перестановок.

ОБОЗНАЧЕНИЯ

Перестановки должны, по крайней мере для этого, быть записаны в циклической записи, где каждый цикл находится в разных скобках, и каждый цикл идет в порядке возрастания. Например (1 2 3 4 5)нет (3 4 5 1 2). А для циклов с одним числом, таких как: (1)(2 3 4)(5)одиночные / фиксированные точки, могут быть исключены значения (1)(2 3 4)(5) = (2 3 4). Но тождество {точка, где все точки зафиксированы (1)(2)(3)(4)(5)} должно быть написано ()так, чтобы просто представлять его.

СОРЕВНОВАНИЕ

Я хотел бы, чтобы в как можно меньшем количестве кода вы взяли любое положительное целое число как вход {1,2,3,4 ...} и отобразили все перестановки альтернативной группы An, где n - вход / все четные перестановки Sn. Например:

Input = 3
()
(1 2 3)
(1 3 2)

а также

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

И как в примерах, я хотел бы, чтобы все циклы одной длины были исключены, а также для идентичности: выходные данные ничего, (){не только в скобках, но с тем, что вы используете для показа различных перестановок} или idявляются приемлемыми.

ДОПОЛНИТЕЛЬНОЕ ЧТЕНИЕ

Вы можете найти больше информации здесь:

• https://en.wikipedia.org/wiki/Permutation
• https://en.wikipedia.org/wiki/Alternating_group

УДАЧИ

И поскольку это - кодовый гольф, тот, кто сможет напечатать перестановки группы переменных An в самых коротких байтах, выигрывает.

Pyth, 26 байт

t#Mf%+QlT2mcdf<>dTS<dTd.pS

          m            .pSQ   Map over permutations d of [1, …, Q]:
             f        d         Find all indices T in [1, …, Q] such that
               >dT                the last Q-T elements of d
              <   S<dT            is less than the sorted first T elements of d
           cd                   Chop d at those indices
   f                          Filter on results T such that
      Q                         the input number Q
     + lT                       plus the length of T
    %    2                      modulo 2
                                is truthy (1)
t#M                           In each result, remove 0- and 1-cycles.

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

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

[8, 4, 6, 3, 10, 1, 5, 9, 2, 7] = (1 8 9 2 4 3 6) (5 10 7)

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

[8, 4, 6, 3, 10, 1, 5, 9, 2, 7] ↦ (8) (4 6) (3 10) (1 5 9 2 7)

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

Mathematica, 84 49 31 байт

GroupElements@*AlternatingGroup

Композиция двух функций. Выходы в виде {Cycles[{}], Cycles[{{a, b}}], Cycles[{{c, d}, {e, f}}], ...}представления (), (a b), (c d)(e f), ....

J , 53 байта

[:(<@((>:@|.~]i.<./)&.>@#~1<#@>)@C.@#~1=C.!.2)!A.&i.]

Циклы в каждой перестановке представлены в виде штучных массивов, поскольку J будет разбитыми массивами с нулевой подкладкой.

Если вывод ослаблен, используя 41 байт

[:((1+]|.~]i.<./)&.>@C.@#~1=C.!.2)!A.&i.]

где каждая перестановка может содержать один цикл и нулевой цикл.

Применение

   f =: [:(<@((>:@|.~]i.<./)&.>@#~1<#@>)@C.@#~1=C.!.2)!A.&i.]
   f 3
┌┬───────┬───────┐
││┌─────┐│┌─────┐│
│││1 2 3│││1 3 2││
││└─────┘│└─────┘│
└┴───────┴───────┘
   f 4
┌┬───────┬───────┬─────────┬───────┬───────┬───────┬───────┬─────────┬───────┬───────┬─────────┐
││┌─────┐│┌─────┐│┌───┬───┐│┌─────┐│┌─────┐│┌─────┐│┌─────┐│┌───┬───┐│┌─────┐│┌─────┐│┌───┬───┐│
│││2 3 4│││2 4 3│││1 2│3 4│││1 2 3│││1 2 4│││1 3 2│││1 3 4│││1 3│2 4│││1 4 2│││1 4 3│││2 3│1 4││
││└─────┘│└─────┘│└───┴───┘│└─────┘│└─────┘│└─────┘│└─────┘│└───┴───┘│└─────┘│└─────┘│└───┴───┘│
└┴───────┴───────┴─────────┴───────┴───────┴───────┴───────┴─────────┴───────┴───────┴─────────┘

Для альтернативной реализации,

   f =: [:((1+]|.~]i.<./)&.>@C.@#~1=C.!.2)!A.&i.]
   f 3
┌─────┬─┬─┐
│1    │2│3│
├─────┼─┼─┤
│1 2 3│ │ │
├─────┼─┼─┤
│1 3 2│ │ │
└─────┴─┴─┘

Желе , 34 28 байт

L€’SḂ
ṙLR$Ṃµ€Ṣ
Œ!ŒṖ€;/Ç€ÑÐḟQ

Попробуй это здесь .

объяснение

Каждая строка в программе Jelly определяет функцию; нижний - « main».

• Первая строка определяет функцию, которая проверяет, является ли произведение цикла нечетным.

  L€      Length of each
    ’     Add 1 to each length 
     S    Take the sum
      Ḃ   Modulo 2
  

• Вторая строка нормализует разбиение перестановки [1…n]на произведение цикла следующим образом:

       µ€    For each list X in the partition:
  ṙLR$          Rotate X by each element in [1…length(X)].
      Ṃ         Get the lexicographically smallest element.
                Thus, find the rotation so that the smallest element is in front.
         Ṣ   Sort the cycles in the partition.
  

  Это превратится, например, (4 3)(2 5 1)в (1 2 5)(3 4).

Вот основная программа. Он принимает аргумент nиз командной строки и:

Œ!              Compute all permutations of [1…n].
  ŒṖ€           Compute all partitions of each permutation.
     ;/         Put them in one big list.
       ǀ       Normalize each of them into a cycle product.
         ÑÐḟ    Reject elements satisfying the top function,
                i.e. keep only even cycle products.
            Q   Remove duplicates.

JavaScript (Firefox 30-57), 220 218 212 211 байт

f=(a,p)=>a[2]?[for(i of a)for(j of f(a.filter(m=>m!=i),p,p^=1))[i,...j]]:[[a[p],a[p^1]]]

К сожалению, 88 байтов достаточно только для генерации знакопеременной группы в виде списка перестановок a, поэтому для преобразования выходных данных в желаемый формат мне потребуется дополнительно 132 130 124 123 байта:

n=>f([...Array(n).keys()],0).map(a=>a.map((e,i)=>{if(e>i){for(s+='('+-~i;e>i;[a[e],e]=[,a[e]])s+=','+-~e;s+=')'}},s='')&&s)

Мне удалось урезать свою версию ES6 до 222 216 215 байт:

n=>(g=(a,p,t=[])=>a[2]?a.map(e=>g(a.filter(m=>m!=e),p,[...t,e],p^=1)):[...t,a[p],a[p^1]].map((e,i,a)=>{if(e>i){for(s+='('+-~i;e>i;[a[e],e]=[,a[e]])s+=','+-~e;s+=')'}},s='')&&r.push(s))([...Array(n).keys(r=[])],0)&&r

GAP , 32 байта

Спасибо @ChristianSievers за сокращение счета пополам.

f:=n->List(AlternatingGroup(n));

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

gap> f(4);
[ (), (1,3,2), (1,2,3), (1,4,3), (2,4,3), (1,3)(2,4), (1,2,4), (1,4)(2,3), (2,3,4), (1,3,4), (1,2)(3,4), (1,4,2) ]