循环置换的合成

2024-03-28 08:41:24 发布

您现在位置:Python中文网/ 问答频道 /正文

什么是计算循环排列组合(从右到左)的好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
在互联网上,我找不到从哪里开始或做什么。有人能帮我吗


Tags: 答案程序算法互联网解决方案
1条回答
网友
1楼 · 发布于 2024-03-28 08:41:24

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

编辑

辛置换可以用作将循环置换组合在一起的函数的构造块。原始问题要求输入和输出字符串。以下是一个示例(您可能需要根据字符串输入进行修改):

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

相关问题 更多 >