高效地将双射转换为循环表示法

Question

考虑以下问题。给定一个长度为n的数组P，表示双射。即元素0<；=i<；n映射到P[i]。在

假设p是一个置换，它可以用循环符号来写，例如here。在

例如，如果

P = [16, 3, 10, 6, 5, 9, 1, 19, 13, 14, 7, 0, 2, 8, 12, 4, 17, 15, 11, 18]

那么循环符号的结果是

^{pr2}$

下面是一个实现这一点的Python方法

def toCycle(p):
    covered = cur = 0 
    perm = []    
    n = len(p)
    done = [0]*n
    while covered < n:
        while cur < n and done[cur] == -1: 
            cur+=1
        cycle = [p[cur]]
        sec = p[p[cur]]
        done[p[cur]] = -1
        done[cur] = -1
        covered+=1
        while sec != cycle[0]:
            cycle.append(sec)
            done[sec] = -1
            sec = p[sec]
            covered+=1
        perm+=[tuple(cycle)]
    return perm

该算法显然是在线性时间内运行的（done/p的每个元素都被访问一个恒定的次数），因此没有多少可以渐近地完成的。在

因为我必须对大量的大排列使用这种方法，所以我想知道

Can you make it faster? Do you have any suggestions for performance improvement?

Answer 1

def cycling(p, start, done):
    while not done[e]:
        done[e] = True
        e = p[e]
        yield e

def toCycle(p):
    done = [False]*len(p)
    cycles = [tuple(cycling(p, 0, done))]
    while not all(done):
        start = done.index(False)
        cycles.append(tuple(cycling(p, start, done)))
    return cycles

在你的例子中，我的代码比你的快30%。在