重新排序列表中的元素，讓連續的元素相互成功？

Question

給定一個大小爲n的項目l的列表，並給出謂詞succeeds(i1,i2)，如果i2成功返回true i1，重新排列l的元素的最佳算法是什麼，以便對於l中的所有項目i，succeeds(i,i.next)返回true？

Answer 1

如果只有一個元素可以成功每個元素，那麼這個問題可以在二次時間內解決。

它實際上是模仿從數據創建鏈表並將其作爲數組返回。瓶頸在於尋找每個元素 - 哪個元素跟隨它。

僞代碼：

specialSort(array,n) 
    create an array a of size n 
    for each i from 0 to n: 
     find j such that succeeds(array[i],array[j]) == true //this may require linear search, so it is O(n) 
     if there is such j: 
      a[i] = j 
     else: 
      a[i] = -1 
    end for 
    find i such that for any j: a[j] != i 
    create empty result array of size n 
    j = 0; 
    while (i != -1): 
     result[j++] = array[i] 
     i = a[i] 
    end while 
    return result 

如果對元素的數量沒有限制，可以成功的每一個元素，那麼@templatrtypedef給你的答案是正確的，你的問題就相當於找到一個哈密爾頓路徑。

編輯：問題是solveable任何良好有序的關係：
注意，如果有可以爲每個元素一個以上的繼任者，但關係succeed()良好有序的[無「循環」]，然後你可以建立從該問題的DAG [每個元素是一個頂點，並且存在對於每對，使得succeed(a,b) == true邊緣]，使用topological orderring - 並返回它。
這也是二次時間，因爲再次 - 瓶頸找到邊緣。

Answer 2

如果對成功關係可以是什麼沒有限制（也就是說，它不一定是傳遞，反身，對稱等），那麼我認爲這個問題是NP-hard的減少NP-hard Hamiltonian path problem。這個簡化實際上很簡單：給定一個圖G，在成功的關係中創建一個圖中的節點數組，使得v成功u如果在原始圖中存在從u到v的邊。通過這種設置，找到一種通過成功關係（連接它們的邊）對數組元素（節點）進行排序的方法相當於在原始圖中查找哈密頓路徑，因爲每個節點只訪問一次。因此，除非P = NP，否則不太可能找到有效的算法。

對不起，我希望這有幫助！