リストの要素を並べ替えると、連続した要素が互いに引き継がれますか？

Question

サイズnのアイテムlのリストが与えられ、i2がi1に成功した場合に真を返す述語が与えられた場合、lのすべてのアイテムiに対してsucceeds(i,i.next)がtrueを返すようなlの要素を並べ替える最適なアルゴリズムは何ですか？

Answer 1

各要素の後に1つの要素しか継承できない場合、この問題は2次時間で解決できます。

実際には、データからリンクリストを作成し、それを配列として返すことを模倣しています。ボトルネックは、各要素（それに続く要素）の発見です。

擬似コード：

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答えが正しいか、そして、あなたの問題は、ハミルトニアンを見つけることと等価ですパス。

EDIT：そして、あなたの各要素のためのより多くのそして1人の後継者が、関係succeed()ができる場合も[NO「ループ」]発注されていないことを
注：この問題は、任意のよく注文した関係ためsolveableですこの問題からDAGを構築することができます[各要素は頂点であり、succeed(a,b) == true]のようなすべての対に対してエッジがあり、topological orderring - を使用して返します。
もう一度 - ボトルネックがエッジを見つけているので、これもまた2次的な時間です。

Answer 2

成功の関係が何であるかに制限がない場合（すなわち、推移的、反射的、対称的なものである必要はない）、この問題はNPから難しいと思いますNP-ハードHamiltonian path problem。この減少は、実際には非常に単純です。グラフGを与えられたグラフのノードの配列を、successor関係で作成し、元のグラフのuからvまでのエッジがある場合はvが成功するようにします。この設定では、配列要素（ノード）を後続の関係（それらを結ぶ辺）で順序付ける方法を見つけることは、元のグラフでハミルトニアンパスを見つけることと等価です。したがって、P = NPでない限り、これに対して効率的なアルゴリズムを見つけることはまずありません。

ご迷惑をおかけして申し訳ありませんが、これが役立ちますようお願いいたします。