ソースと最終配列が与えられた場合、2次の時間の複雑さよりも小さい値でソースからfinalを生成するホップ数を見つけてください。

Question

整数の配列があるとします（例：[1 5 3 4 6]）。要素は次の規則に従って再配置されます。すべての要素は前方に（左に向かって）飛び越えて、その要素が飛び越した指数でスライドできます。プロセスは、第2のインデックス（すなわち、5）の要素から始まる。要素1をホップするか、独自の位置にとどまるかを選択できます。ホップすることを選択すると、要素1がインデックス2にスライドします。ホップすることを選択し、結果の配列が[5 1 3 4 6]。エレメント3は1または2ポジションでホップでき、プロセスが繰り返されます。 1つの位置を3ホップ上回ると、配列は[5 3 1 4 6]になり、2つの位置をホップすると[3 5 1 4 6]になります。

要素のすべての可能な置換がこのように可能であることを示すことは非常に容易です。また、最終的な構成には、固有の一連の発生によって到達することができます。

最後の配列とソース配列が与えられたら、ソースから最終配列に到達するために必要なホップの総数を求めます。 O（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）を作成するたびにマップを更新する必要があります。

P.S.私はベイジアンの2つの順列の間の相関関係をモデル化しようとしていますが、これはそれの副次的な問題です。問題を簡単にするために生成プロセスを変更することについてのアイデアも役立ちます。

編集：私は自分の答えを見つけました。これはまさにケンドール・タウの距離です。これをO（NlogN）で見つける簡単なマージソートベースのアルゴリズムがあります。

Answer 1

ターゲット配列を順序付けすることを検討してください。ターゲット配列[2 5 4 1 3]は、再ラベル付けするだけで[1 2 3 4 5]と見なすことができます。一定の時間内に要素を比較できるようにするには、マッピングを知る必要があります。この場合、4と5を比較するには、index[4]=2 > index[5]=1（ターゲット配列内）と4 > 5（つまり、4は最後に5の右側にある必要があります）をチェックします。

あなたが本当に持っているのは、バニラの並べ替えの問題です。順序は、通常の数値順序とはまったく異なります。変更されるのは比較関数だけです。残りは基本的に同じです。並べ替えはO(nlgn)、またはさらにO(n)（基数ソート）で行うことができます。つまり、いくつかの追加の制約があります。つまり、インプレースをソートしなければならず、2つの隣接する要素だけを交換することができます。

強力で単純な候補者はselection sortであり、これはちょうどO(n^2)時に実行されます。各反復で、「配置されていない」部分の「最も残っている」残りの要素を特定し、「配置された」部分の最後に着くまでスワップします。適切なデータ構造（O(lgn)時間に "最も残った"最も左の要素を識別するための優先度キュー）を使用して、O(nlgn)に改善することができます。nlgnは比較ベースのソートの下限であるため、私はあなたがそれよりもうまくいくとは思っていません。

編集：スワップのシーケンスにはまったく関心がありません。スワップの順序は必要ありません。これは正確に配列内のinversionsの番号です（特定のニーズに合わせて調整されます： "非自然順序付け"比較関数ですが、数学は変更されません）。そのアサーションの証明については、this answerを参照してください。

逆数の数を見つける1つの方法は、マージソートアルゴリズムを適合させることです。配列を実際にソートして計算する必要があるので、それでもまだ時間はO(nlgn)です。実装については、this answerまたはthisを参照してください（ここでもまた適応する必要があります）。

Answer 2

あなたの答えから、ホップ数は元の配列を最終配列に変換するのに必要な隣接要素のスワップの総数であると仮定します。

私は、挿入の並べ替えのようなものを使用することをお勧めしますが、挿入部分はありません。配列のデータは変更されません。

ストールされたホッパーのカウンタを、カウンター（サブツリー内の要素の数）を持つ平衡バイナリー検索ツリーとして作成することができます。

あなたがCはトン内の要素の数である（Cログ）時間を、トン、バランストンから要素を削除して、Oでトンの要素位置を見つけ、トンに要素を追加することができ。

要素の位置を特定する単語がほとんどありません。これは、スキップされた左辺の累積を伴うバイナリ検索（およびブランチ上の要素を保持する場合は中間の要素+1）カウントで構成されます。

バランス/追加/削除に関する単語がほとんどありません。削除された/追加された要素/サブツリーと更新カウンターから上方に移動する必要があります。インサート+バランスおよび除去+バランスのための操作の全体数はO（ログC）のままです。

レッツトンは（平衡探索木）キューは、P現在の元の配列インデックス、は、元の配列は、最終的なアレイは F ある最終配列インデックスであるQがあることです。

今度は、左サイドから出発1つのループ（たとえば、P = 0、Q = 0）を有する： F

• 場合 [P] == を[q]、元の配列要素がキュー全体をホップします。応答にt.countを追加し、増分p、増分qを追加します。

• = F [Q]と F [Q]がTでない [P] 場合！、次いでに [P]を挿入tおよび増分p。

• [P]！= トンである[Q]とF [Q] fは、その後、追加F [Q]回答するキュー内の位置ならば、削除f [q] tおよび増分qから、

私は、配列が実際には1つの配列の並べ替えである場合、このプロセスがpとqを同時に末尾に移動させる魔法が好きです。それにもかかわらず、pとqがオーバーフローして不正なデータが検出された場合は、実際にデータが正しいことを証明する手段がないためです。