轉換置換中的反轉表示

第一 N自然數

排列P = [a1, a2, ... , aN]可以通過inversionsI = [i1, i2, ... , iN]的列表，其中iK告訴我們有多少是數字大於K可以在置換PK之前發現來表示。轉換置換中的反轉表示

示例：如果P = [3, 1, 4, 2]，然後I = [1, 2, 0, 0]（放置3，1,3和4放置在2之前，而3和4之前沒有任何更大的數字）。

有一個顯而易見的算法，可以將標準的排列轉換爲反轉形式，並在O(N^2)（我們只是按照定義和計數）運行。對於逆轉換（這稍微不那麼簡單）也是如此。

是否有算法具有較低的時間複雜度？

2016-01-06 Antoine

我認爲有可能使用Fenwick樹或類似的數據結構。 – kfx

有一個簡單的迭代動態規劃算法來解決這個問題：對於所有的i從1到n（排列的長度）取數i，看看有多少P元素留下的i已經看到。由於我們按遞增順序處理i，我們知道而不是所見的元素大於i - 因此我們計算並記錄這些元素的數量。訣竅是引入一個外部列表，而不是跟蹤P中的哪些元素已經被看到。

首先，讓我們看看如何以O(n^2)的方式做到這一點。

創建初始化爲零的結構tree：例如，如果P=[4, 3, 2, 1]，則算法將如下執行。如果P中的第j個位置的元素已被迭代算法看到，則它在位置j中保持「1」。
取1，確定pos==3。在tree[pos]中寫下「1」。計算num_seen=sum(tree[0:3])等於0.記下pos - num_seen + 1在I[0]。在此之後：tree = [0, 0, 0, 1], I = [3, 0, 0, 0]
取2，在樹[1]中寫下「1」，在I [1]處寫下1。。取3，在樹[2]中寫下「1」，在I [2]寫下0。 tree = [0, 1, 1, 1], I=[3,1,0,0]。
取4，在樹[0]中寫下「1」，在I [3]寫下0。 tree = [1, 1, 1, 1], I=[3,1,0,0]。

第二特技是使用有效的數據結構來計數O(n log n)時間，而不是如上述的O(n^2)可見元件的數量。

這裏是一個使用樹狀數組數以快速的方式看到的元素個數Python代碼：

def ft_sum(tree, a, b): 
    if a == 0: 
     s = 0; 
     while b >= 0: 
      s += tree[b]; 
      b = (b & (b + 1)) - 1 
     return s 
    return ft_sum(tree, 0, b) - ft_sum(tree, 0, a - 1) 

def ft_adjust(tree, k, v): 
    while k < len(tree): 
     tree[k] += v 
     k |= k + 1 

def calcI(P): 
    n = len(P) 
    tree = [0] * n 
    I = [0] * n 
    positions = [0] * n 
    for i in xrange(n): 
     positions[P[i]-1] = i 
    tree = [0] * n 
    for i in xrange(n): 
     pos = positions[i] 
     ft_adjust(tree, pos, 1) 
     num_seen = ft_sum(tree, 0, pos) 
     I[i] = pos - num_seen + 1 
    return I

來源

2016-01-06 11:35:30 kfx

謝謝你的努力！我也欣賞真正的代碼（不只是僞）。爲了它的完整性，我會接受你的答案，而不是我的:) – Antoine

同時，我發現了一個簡單的解決方案，對於僞代碼，這在O(n log n)工作，也。

initialize AVL-tree T 
initialize array I of length n 
for i = 1, 2, ... , n: 
    I[P[i]] = T.countGreaterThan(P[i]) 
    T.add(P[i])

來源

2016-01-06 12:45:05 Antoine

轉換置換中的反轉表示

回答

相關問題