この問題は、オブジェクトの配列 (順序付きセット) の同期で発生します。
具体的には、別のコンピューターに同期されたアイテムの配列を考えてみましょう。ユーザーは 1 つまたは複数のオブジェクトを移動して、配列を並べ替えます。プログラムが起動すると、新しい順序が表示され、古い順序がわかりました。変更を別のコンピューターに送信し、そこで新しい順序を再現する必要があります。次に例を示します。
index 0 1 2
old order A B C
new order C A B
移動を、特定のオブジェクトを特定の新しいインデックスに移動することとして定義します。問題は、通信リンクを介して最小数の移動を送信することによって並べ替えを表現することです。これにより、反対側は、移動されていないオブジェクトを古い順序で取得し、それらを新しい順序でまだ使用されていないインデックスに移動することにより、残りの移動を推測できます。最低のインデックスから始まり、上に向かっていきます。この転送方法は、少数のオブジェクトが大きな配列内で移動され、多数のオブジェクトが移動する場合に非常に効率的です。
ちょっとまって。例を続けましょう。我々は持っています
CANDIDATE 1
Move A to index 1
Move B to index 2
Infer moving C to index 0 (the only place it can go)
最初の 2 つの手を送信する必要があることに注意してください。Move B をインデックス 2に送信しない場合、B はインデックス 0 に推論され、最終的に BAC になりますが、これは誤りです。2 つの手を送信する必要があります。もっとうまくやれるか見てみましょう…</p>
CANDIDATE 2
Move C to index 0
Infer moving A to index 1 (the first available index)
Infer moving B to index 2 (the next available index)
この場合、正しい答え CAB が得られ、Move C をインデックス 0 に1 つだけ送信します。したがって、候補 2 は候補 1 よりも優れています。さらに 4 つの候補がありますが、何かを行うには少なくとも 1 つの手が必要であることは明らかなので、ここでやめて、候補 2 が勝者であると宣言できます。
考えられるすべての候補を力ずくで試すことでこれを行うことができると思いますが、N個のアイテムの配列にはN個あります! (N factorial) 可能な候補であり、例のように不必要な検索を切り捨てるほど賢くても、何百ものオブジェクトを含む可能性のある典型的な配列では、依然としてかなりのコストがかかる可能性があります。
互換性のために、別のプログラムの送信をエミュレートする必要があるため、注文全体を送信するだけの解決策は受け入れられません。
誰かが答えを書き留めることができればそれは素晴らしいことですが、コンピュータ サイエンスの教科書 XXX の第 N 章を読むようにというアドバイスはまったく受け入れられます。私はただの電気技師なので、それらの本は知りません。
ありがとう！
ジェリー・クリノック