用循环表示法打印对称群Sn的“偶”排列

Question

任务

定义

考虑点{1,2,3,4,5}及其所有排列。我们可以通过一个简单的技巧来找出这5点可能排列的总数:用这些点填充5个插槽，第一个插槽将有5个可能的数字，第二个4(因为一个用来填充第一个插槽)，第三个插槽，等等。因此，排列的总数是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长的循环x偶数
2. (1 2 3 4 5) =无偶数长度圈，奇偶环，注意如果不存在偶数长度圈，则置换为偶数。

奇怪的例子：

1. (1 2)(3 4 5) =一个2长圈的奇数
2. (1)(2 3 4 5) =一个4长的循环

由于任何对称群中一半的置换是偶数，所以我们可以称偶数群为交替群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)

和在示例中一样，我希望对所有长度为1的循环进行省略，至于标识: nothing的输出，() {不仅是括号，而且是用来显示不同排列}或id的任何东西都是可以接受的。

额外阅读

您可以在这里找到更多信息：

• https://en.wikipedia.org/wiki/Permutation
• https://en.wikipedia.org/wiki/Alternating_组

祝你好运

因为这是合作伙伴，谁能以最短的字节打印交替组的排列，就会获胜。

Answer 1

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)(15 9 2 7)

为了扭转这一双射，我们可以采用循环形式的任意排列，旋转每个圈，使其最小数为第一个，对圈进行排序，使它们的最小数以递减的顺序出现，并擦除所有括号。

Answer 2

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│ │ │
└─────┴─┴─┘

Answer 3

空隙，32字节

感谢“基督教学人”，因为他把数量减少了一半。

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) ]