4

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

更正式地说，我有两个唯一 ID（字符串）数组，称为user_columns和server_columns。我想重新订购server_columns，以便我尊重来自 的所有订购信息user_columns，并尽可能多地来自server_columns。我该怎么做呢？“尽可能”的合理正式定义是什么？

到目前为止我的分析：

问题的一个方面是微不足道的：如果服务器删除了一些列，则从user_columns. 有关不再存在的列排序的任何信息都没有实际意义。那么问题就变成了合并两个可能相互冲突的订购信息集之一。

这对应于投票理论中的一系列问题：给定一组选票，每张选票都包含候选人之间的部分顺序，产生候选人的完整顺序，这在某种意义上反映了选票。

这使我认为，通过将Schulze Method或Ranked Pairs应用于基于user_columns和的一组充分操纵的选票，我可能会得到一个可行的解决方案server_columns。出于用户体验的原因，通过在最后（右侧）插入新列来打破联系对我来说似乎是个好主意。

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

还要注意，我们可以考虑三种比较：A 和 B 都在 中user_columns，其中之一是，或者都不是。前一种和后一种很容易解决（分别参考user_columns和server_columns）；中间的那个，以及它与后者的交互，是棘手的部分。

4

3 回答 3

4

假设我们有C列，编号从1到C。我们有两个列序列，U = u 1 , u 2 , ... u n 和S = s 1 , s 2 , ... s m。我们想要找到S的一个排列P，使得P没有关于U的反转和关于S的最小数量的反转。

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

我们可以应用动态规划来找到最优交织：令 A = (a i ) = U ∩ S 且 B = (b j ) = S \ U。令f (i,j)为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]))

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

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

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

这是算法的实现，请原谅我缺乏JS技能。

于 2014-03-22T05:14:16.410 回答
1
于 2014-03-23T10:44:26.843 回答
1

一种可能合理的定义是最小化与服务器顺序相关的反转次数，但要遵守对两个顺序的共同列的限制相等的约束。我不知道一种算法来最小化这个目标。

于 2014-03-21T22:59:53.590 回答