algorithm - 合并两个部分(共同超定)的订购信息集

Question

我有一个在网格中包含数据的网络应用程序。用户可以对列重新排序，服务器可以更改存在的列。我想将用户的列顺序保存在 cookie 中并在页面加载时恢复它。

更正式地说，我有两个唯一 ID(字符串)数组，分别称为 user_columns 和 server_columns。我想对 server_columns 重新排序，以便我尊重 user_columns 中的所有 排序信息，以及来自 server_columns 的排序信息> 尽可能。我该怎么做呢？ “尽可能”的合理正式定义是什么？

到目前为止我的分析:

问题的一个方面是微不足道的:如果服务器删除了一些列，请从 user_columns 中删除相应的条目。有关不再存在的列的排序的任何信息都没有实际意义。然后，问题就变成了合并两组可能相互冲突的订购信息。

这对应于投票理论中的一系列问题:给定一组选票，每张选票都包含候选人之间的偏序，产生候选人的完整排序，这在某种意义上反射(reflect)了选票。

这让我想到我可能会通过应用例如Schulze Method或 Ranked Pairs基于 user_columns 和 server_columns 的一组充分操纵的选票。出于用户体验的原因，通过在最后(右侧)插入新列来打破联系对我来说似乎是个好主意。

这听起来像是在正确的轨道上吗？

另请注意，我们可以考虑三种比较:A 和 B 都在 user_columns 中，其中一个在，或者都不在。前者和后者很容易解决(分别引用user_columns和server_columns)；中间的那个及其与后者的交互是棘手的部分。

Answer 1

假设我们有 C 列，编号从 1 到 C。我们有两个列序列，U = u₁, u₂, ... u_n 和S = s₁, s₂, ... s_m。我们想找到 S 的排列 P，这样 P 就 U 和 a 没有反转关于 S 的最少反转次数。

我们可以证明存在这样一个最优的P，它是U∩S和S\U的交错。 “交错”是指 P 没有关于 U ∩ S 或 S\U 的反转。

我们可以申请dynamic programming找到最佳交织:设 A = (a_i) = U ∩ S 和 B = (b_j) = S\U。令 f(i ,j) 是反转次数 w.r.t. S A 的前缀 a_1...i 和 B 的 b_1...j 的最优交错。这个想法是与 longest common subsequence 非常相似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]))

我在这里使用符号 [1 if X] 表示值 1，如果 X 为真，0，如果 X 为真错误。

矩阵 f 可以在 O(|A|^2 * |B|^2) 时间内构建。最小成本(反转次数 w.r.t. S)将为 f(|A|, |B|)。

我们也可以使用 DP 矩阵重建最优排列:我们从后到前构建它。我们从元组 (i,j) = (|A|, |B|) 开始，在每一步取决于两个选项中哪一个在 DP 转换中最小，我们知道我们是否需要将 A[i] 或B[j] 到排列的前面。然后我们根据我们的选择继续 (i-1, j) 或 (i, j-1)。

Here is an implementation of the algorithm ，请原谅我缺乏 JS 技能。