计算排列列表中的循环

Question

我正在尝试制作一个函数来计算排列列表中的循环数。

我有时会在运行代码时得到正确的答案，但大多数时候我会收到一条错误消息 - 我无法弄清楚原因。

我的代码如下：

def count_cycles(n):

    cycle_count = 0
    copy_list = []
    
    for element in n:
        copy_list.append(element)

    while len(copy_list) != 0:
        ran_num = random.choice(copy_list)

        while True:
            if n[ran_num] == ran_num:
                cycle_count = circle_count + 1
                if int(ran_num) in copy_list:
                    copy_list.remove(ran_num)
                    
                break
            
            else:
                n.insert(ran_num, ran_num)
                print(n, ran_num, copy_list)
                ran_num = n[ran_num + 1]
                
                print(ran_num)
                copy_list.remove(ran_num)
                    
                n.remove(ran_num)
                continue

    return print(cycle_count, n)

我使用的是我用这个排列列表测试了3个周期[2, 6, 0, 3, 1, 4, 5]。

Picture of output from a correct and incorrect run

我用print(n, ran_num, copy_list)根据图片评估输出。

Answer 1

这是一种可能性：

p = [2, 6, 0, 3, 1, 4, 5]

cycles = set()
elts = set(range(len(p)))
while elts:
    cycle = []
    x0 = elts.pop()
    cycle.append(x0)
    x = p[x0]
    while x != x0:
        cycle.append(x)
        x = p[x]
    elts -= set(cycle)
    cycles.add(tuple(cycle))
    
print(cycles)

它给出：

{(0, 2), (1, 6, 5, 4), (3,)}

然后要获得可以使用的循环数 len(cycles)。

Answer 2

除了现有答案之外，sympy 还提供了一些处理排列的功能。在这种情况下，您可以使用以下内容：

from sympy.combinatorics import Permutation
p = Permutation([2, 6, 0, 3, 1, 4, 5])
num_cycles = p.cycles # 3

计算排列列表中的循环

Count cycles in a permutated list

python

algorithm

list

permutation