有效地將雙射投影轉換爲週期符號

考慮以下問題。給定是長度爲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]

那麼結果在週期符號將是

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

以下是一個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的每個元素被訪問的次數是固定的），因此沒有mu可以漸近地完成。

正如我不得不使用這種方法對大量大排列的我想知道

你能使其更快？你有什麼建議改善性能？

來源

2014-12-26 Jernej

鑑於您必須訪問列表中的每個條目才能轉換列表，所以您無法做得比線性更好。但是，如下面的答案所示，可以稍微減少線性算法的係數... – twalberg

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％。

來源

2014-12-26 15:24:06 BurningKarl

有效地將雙射投影轉換爲週期符號

回答

相關問題