algorithm - 順序付け情報の 2 つの部分的な (共に過剰決定された) セットのマージ

Question

グリッドにデータを含む Web アプリがあります。ユーザーは列を並べ替えることができ、サーバーは存在する列を変更できます。ユーザーの列の順序を Cookie に保存し、ページの読み込み時に復元したいと考えています。

より正式には、 と と呼ばれる一意の ID (文字列) の 2 つの配列がuser_columnsありserver_columnsます。からのすべての注文情報を可能な限りserver_columns尊重するように再注文したいと思います。どうすればいいですか？「可能な限り」の合理的な正式な定義は何ですか?user_columnsserver_columns

これまでの私の分析：

問題の 1 つの側面は些細なことです。サーバーがいくつかの列を削除する場合は、対応するエントリを から削除しますuser_columns。もはや存在しない列の順序に関する情報は意味がありません。問題は、競合する可能性のある 2 つの順序付け情報セットをマージすることになります。

これは、投票理論の一連の問題に対応します。それぞれが候補間の半順序を含む一連の投票が与えられると、ある意味で投票を反映する候補者の完全な順序が生成されます。

これにより、シュルツ法またはランク付けされたペアuser_columnsなどを、およびに基づいて十分に不正に操作された投票セットに適用することで、実行可能な解決策が得られるのではないかと思いますserver_columns。UX の理由から、新しい列を最後 (右側) に挿入して関係を断ち切ることは、私には良い考えのように思えます。

これは正しい軌道に乗っているように聞こえますか?

また、3 種類の比較を考慮することができることにも注意してくださいuser_columns。前者と後者は簡単に解決できます (それぞれuser_columnsとを参照server_columns)。真ん中にあるものと、後者との相互作用は、注意が必要な部分です。

Answer 1

1からCまで番号が付けられたC列があるとします。U = u ₁ , u ₂ , ... u _n とS = s ₁ , s ₂ , ... s _mの 2つの列シーケンスがあります。PがUに関して反転を持たず、 Sに関して最小数の反転を持たないように、 Sの順列Pを見つけたいと考えています。

U ∩ SとS \ Uのインターリーブであるような最適なPがあることを示すことができます。「インターリーブ」とは、U ∩ SまたはS \ Uに関してPに反転がないことを意味します。

動的計画法を適用して、最適なインターリービングを見つけることができます。 A = (a _{i ) = U ∩} Sおよび B = (b _j ) = S \ Uとします。 Aのプレフィックス a _1...iと B の b _{1...jの最適なインターリーブ。この考え方は、}最長共通サブシーケンスDP アルゴリズムに非常に似ています。再発があります

f(0,j) = 0 for all j >= 0
f(i,0) = f(i-1, 0) + sum(k=1 to i-1, [1 if A[i] appears before A[k] in S])
f(i,j) = min(f(i-1, j) + sum(k=1 to i-1, [1 if A[i] appears before A[k] in S])
                       + sum(k=1 to j, [1 if A[i] appears before B[k] in S]),
             f(i, j-1) + sum(k=1 to i, [1 if B[j] appears before A[k] in S])
                       + sum(k=1 to j-1, [1 if B[j] appears before B[k] in S]))

ここでは、 X が true の場合は、X が false の場合[1 if X]は という値を表すために表記法を使用しました。10

行列fは時間 O(|A|^2 * |B|^2) で作成できます。最小コスト (S に関する反転の数) はf(|A|, |B|)になります。

DP 行列を使用して最適な順列を再構築することもできます。後ろから前に構築します。タプル (i,j) = (|A|, |B|) から開始し、DP 遷移で 2 つのオプションのどちらが最小であるかに応じて、すべてのステップで、A[i] またはB[j] を順列の前に。次に、選択に応じて (i-1, j) または (i, j-1) に進みます。

これがアルゴリズムの実装です。私の JS スキルの不足を許してください。

Answer 2

合理的な定義の 1 つは、2 つの順序に共通する列に対する制限が等しいという制約の下で、サーバーの順序に対する反転の数を最小限に抑えることです。この目的を最小限に抑えるためのアルゴリズムを手に負えません。

Answer 3