整数の配列があるとします (例: [1 5 3 4 6])。要素は、次の規則に従って再配置されます。すべての要素は前方 (左方向) にホップし、ホップしたインデックス内の要素をスライドできます。プロセスは、2 番目のインデックス (つまり 5) の要素から開始します。要素 1 を飛び越えるか、それ自体の位置にとどまるかを選択できます。要素 1 が飛び越えることを選択した場合、要素 1 はインデックス 2 までスライドします。飛び越えることを選択したと仮定し、結果の配列は [5 1 3 4 6]。要素 3 は 1 つまたは 2 つの位置を飛び越えることができ、プロセスが繰り返されます。1 つの位置を 3 回ホップすると、配列は [5 3 1 4 6] になり、2 つの位置をホップすると [3 5 1 4 6] になります。
このようにして、要素のすべての可能な順列が可能であることを示すのは非常に簡単です。また、一意のオカレンス セットによって、最終的な構成に到達することもできます。
問題は、最終配列とソース配列が与えられた場合、ソースから最終配列に到達するために必要なホップの総数を見つけることです。AO(N^2) の実装は簡単に見つかりますが、これは O(N) または O(NlogN) で実行できると思います。また、O(N2) よりもうまくできない場合は、それを知っておくとよいでしょう。
たとえば、最終配列が [3,5,1,4,6] でソース配列が [1,5,3,4,6] の場合、答えは 3 になります。
私の O(N2) アルゴリズムは次のようなものです。移動する最後の要素であることがわかっているため、ソース配列のすべての位置を最後からループします。ここでは 6 になり、最終的な配列での位置を確認します。必要なホップ数を計算し、最終的な配列を再配置して、その要素をソース配列の元の位置に配置する必要があります。再配置ステップは配列内のすべての要素を対象とし、プロセスはすべての要素をループするため、O(N^2) になります。ハッシュマップまたはマップを使用すると検索に役立ちますが、O(N^2) になるすべてのステップの後にマップを更新する必要があります。
PSベイジアンの方法で2つの順列間の相関をモデル化しようとしていますが、これはそのサブ問題です。問題をより単純にするために生成プロセスを変更するアイデアも役に立ちます。
編集：答えが見つかりました。これは、まさにケンドール タウ距離が行うことです。O（NlogN）でこれを見つけるための簡単なマージソートベースのアルゴリズムがあります。