一组排列的轨道

Question

在GAP中，我们可以很容易地找到一组排列的轨道：

grp := Group([ (1,2,3,4,5), (1,2,4,3) ]);;
els := Elements(grp);;
O := Orbit(grp, els{[1,2,3,4]}, OnSets);

[ [ (), (2,3,5,4), (2,4,5,3), (2,5)(3,4) ], [ (), (1,3)(4,5), (1,4,3,5), (1,5,3,4) ],
  [ (), (1,2,5,4), (1,4,5,2), (1,5)(2,4) ], [ (), (1,2)(3,5), (1,3,2,5), (1,5,2,3) ],
  [ (), (1,2,4,3), (1,3,4,2), (1,4)(2,3) ] ]

我想在 Sage 中执行此操作（最好不调用 GAP 接口）。在文档中，我发现了以下内容：http://doc.sagemath.org/html/en/reference/groups/sage/groups/perm_gps/permgroup.html#sage.groups.perm_gps.permgroup.PermutationGroup_generic.orbit

他们提供了以下 "OnSets" 示例：

sage: S3 = groups.permutation.Symmetric(3)
sage: S3.orbit((1,2), action = "OnSets")
({1, 2}, {2, 3}, {1, 3})

所以我尝试了以下方法：

grp = PermutationGroup([ '(1,2,3,4,5)', '(1,2,4,3)' ])
els = list(grp)
grp.orbit(els[:4], action = "OnSets")

TypeError: unhashable type: 'list'

有人知道如何正确计算吗？目前，我正在使用 gap.eval:

解决这个问题

gap.eval("grp := Group([ (1,2,3,4,5), (1,2,4,3) ])")
gap.eval("els := Elements(grp)")
gap.eval("test_orbit := Orbit(grp, els{[1,2,3,4]}, OnSets)")
O = gap.new("test_orbit")

现在我使用 'O' 进行的任何计算都非常慢，所以我想尝试在 Sage 中做所有事情，或者以某种方式将 'O' 转换成一个可以快速处理的合适的 Sage 对象.

Answer 1

这归结为不知何故 Sage 没有准备好递归地处理这个输入。这是相关代码（您可以通过执行 grp.orbit?? 找到它）：

    def input_for_gap(x, depth, container):
        if depth == len(container):
            try:
                return self._domain_to_gap[x]
            except KeyError:
                raise ValueError('{0} is not part of the domain'.format(x))
        x = [input_for_gap(xx, depth+1, container) for xx in x]
        if container[depth] is Set:
            x.sort()
        return x

但是 grp._domain_to_gap 产生字典 {1: 1, 2: 2, 3: 3, 4: 4, 5: 5}，这显然不会对 () 甚至其他元素做很多有趣的事情（这是第二次通过递归它将会发生）。

问题是这里还需要再递归一层，但是不知为何没有考虑。我为此打开了Ticket 29151。

Answer 2

虽然我无法让 Sage 'orbit' 命令正常工作，但我可以通过直接实现该函数来计算所需的轨道。在 GAP 中，函数： Orbit(grp, els{[1,2,3,4]}, OnSets) 通过 els 中的每个 y 的共轭，使 grp 中的 x 作用于 els{[1,2,3,4]}；即 xyx^{-1}。我已经使用以下方法在 Sage 中实现了这一点：

grp = PermutationGroup([ '(1,2,3,4,5)', '(1,2,4,3)' ])
indices = [1,2,3,4]
els = list(grp)
perm = [els[i-1] for i in indices] #Convert 'indices' into permutations from 'els'

O = []
for x in els:
    temp_O = []
    for y in perm:
        temp_O.append(x*y*x.inverse()) #Conjugation step

    if (temp_O in O) == False:
        O.append(temp_O)

然后O = [[(), (1,5,4,3,2), (1,4,2,5,3), (1,3,5,2,4)], [(), (1,2,3,4,5), (1,3,5,2,4), (1,4,2,5,3)], [(), (1,4,2,5,3), (1,2,3,4,5), (1,5,4,3,2)], [(), (1,3,5,2,4), (1,5,4,3,2), (1,2,3,4,5)]]。

请注意，虽然这与上面的 O 不同（在 GAP 中），但 GAP 和 Sage 对组的排列进行索引的方式不同（不同的顺序）；即索引 [1,2,3,4] 对应于每个程序中的不同排列。这两个函数确实 return 具有相同的值。上面编写的脚本（在 Sage 中）的计算速度与 GAP 的 Orbit 函数相当。

Answer 3

在示例中，所讨论的集合是一个子组；那么更好的方法是在陪集上构建一个动作。

此外，我们不推荐使用 GAP pexpect 接口，而是使用 libgap。那么你的例子可以这样写（我只用了另一种方式来创建要作用的排列子集）：

sage: grp = libgap(PermutationGroup([ '(1,2,3,4,5)', '(1,2,4,3)' ])); grp
Group([ (1,2,3,4,5), (1,2,4,3) ])
sage: s=grp.Stabilizer(1)
sage: grp.Orbit(s.Elements(),libgap.OnSets)
[ [ (), (2,3,5,4), (2,4,5,3), (2,5)(3,4) ], [ (), (1,3)(4,5), (1,4,3,5), (1,5,3,4) ], [ (), (1,2,5,4), (1,4,5,2), (1,5)(2,4) ], [ (), (1,2)(3,5), (1,3,2,5), (1,5,2,3) ], [ (), (1,2,4,3), (1,3,4,2), (1,4)(2,3) ] ]

一组排列的轨道

Orbit of a set of permutations

sage