循环置换的组成

Question

什么是一个好的Python程序来计算循环排列的组成(从右到左)？我知道如何计算答案，但我不知道Python程序的算法。

例如，'(1,6,5,3)(1,4,2,3)‘的解为'(1,4,2)(3,6,5)’。因为1-4- 4，4-2- 2，2-3-1和3-1- 6，6-6- 5，5-5-3

在互联网上，我找不到从哪里开始，也不知道该做什么。有人能帮帮我吗？

Answer 1

Sympy包很好地处理循环排列。您编写排列的方法称为“不相交循环表示法”。下面是一个使用你的周期的例子：

from sympy.combinatorics.permutations import Permutation

a = Permutation([[1, 6, 5, 3]])  
b = Permutation([[1, 4, 2, 3]])

new_perm = b * a

这将给出new_perm的输出(142)(365)。

对于这些周期中的任何一个，您都可以像调用函数一样调用它们。例如，我们可以将1输入到new_perm，并期望4作为输出：

> new_perm(1)
4

编辑

Sympy排列可以用作将循环排列组合在一起的函数的构件。最初的问题要求输入和输出字符串。下面是一个示例(您可能需要根据您的字符串输入进行修改)：

import re
import functools

def compose_cycles(input_string):
    # Split the cycles by regex
    cycles = re.findall("\(([\d,]+)\)", input_string)

    # Break each cycle into a list of integers
    cycles = [list(map(int, x.split(","))) for x in cycles]

    # Make each cycle into a Sympy Permutation
    cycles = [Permutation([x]) for x in cycles]

    composition = functools.reduce(lambda x, y: y * x, cycles)

    return str(composition)

compose_cycles('(1,6,5,3)(1,4,2,3)')

函数的最后一行调用str，它返回字符串表示(而不是原始排列)。我们的输出是'(1 4 2)(3 6 5)'