我有一个在网格中的数据web应用程序。用户可以对列重新排序，服务器可以更改存在哪些列。我想将用户的列顺序保存在cookie中，并在页面加载时恢复它。
更正式地说，我有两个唯一id(字符串)数组，称为user_columns和server_columns。我想重新排序server_columns，这样我就尊重user_columns的所有排序信息，并尽可能多地尊重server_columns。我该怎么做呢?"尽可能多"的合理正式定义是什么?
我目前的分析:
这个问题的一个方面是微不足道的:如果服务器删除了一些列，那么从user_columns中删除相应的条目。关于不再存在的列的排序的任何信息都是没有意义的。然后，问题就变成了合并两组可能冲突的排序信息。
这对应于投票理论中的一系列问题:给定一组选票，每一张选票都包含候选人之间的偏序，产生一个候选人的完全顺序，在某种意义上反映了选票。
这让我认为我可能会得到一个可行的解决方案，例如应用舒尔茨方法或排名对基于user_columns和server_columns的一组充分操纵的选票。出于用户体验的考虑，在最后(在右边)插入新列来打破联系对我来说似乎是个好主意。
这听起来像是在正确的轨道上吗?
还请注意，我们可以考虑三种比较:A和B都在user_columns中，其中一个在，或者它们都不在。前一种和后一种很容易解决(分别参考user_columns和server_columns);中间的一个，以及它与后者的相互作用，是棘手的部分。
假设我们有C列，编号从1到C。我们有两个列序列，U = U 1， U 2，…u n <子>和 =年代 <子> 1,S <子> 2 ,…m s <子>。我们想要找到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 1的最优交错的逆序个数，S…i (A) and b(1)…j (b)的思想与最长公共子序列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可以在时间0 (|A|^2 * |B|^2)内构建。最小代价(倒排次数)为f(|A|， |B|)。
我们也可以使用DP矩阵重建最优排列:我们从后到前构建它。我们从元组(i,j) = (|A|， |B|)开始，在每一步，根据两个选项中哪一个在DP转换中最小，我们知道我们是否需要将A[i]或B[j]放在排列的前面。然后根据我们的选择继续(i-1, j)或(i, j-1)
这是一个算法的实现，请原谅我缺乏JS技能。
一个合理的定义可能是最小化相对于服务器顺序的倒排数量，但要遵守对两个顺序的公共列的限制相等的约束。我不知道一个算法来最小化这个目标。
这与Niklas B的回答有关:
定理:考虑某有序集(如整数)的序列S = S₁，…，S₁。If i
直观地说:如果两个元素无序，你交换它们，你更接近于得到一个有序的列表。
:观察到的唯一元素有不同的相对顺序和年代" ( Sᵢ, Sⱼ), ( Sᵢ, Sₖ)和( Sⱼ, Sₖ)为每个 k , 我& lt;k & lt;。我们知道(s l ， sⱼ)是s 的反转，但不是s '，因此考虑sₖ对于某些这样的k。 为ₖ或 Sⱼ或 Sⱼ(我们假设 s 的元素是唯一的)。 ( sᵢ, sₖ)是一个倒置的和( sⱼ, sₖ)是一个反演在年代"。在第二种情况下,( sᵢ, sₖ)和( sⱼ, sₖ)反演在但不是在 " 。第三,( sⱼ, sₖ)是一个倒置的和( sᵢ, sₖ)。这些都是逆序的变化 在每种情况下，S'中的逆序数要么与S中的逆序数相同，要么更小。回想一下(s ` ` ， s ` `ⱼ)从s 固定到s ` ` ，我们得到了期望的结果。■ 因此,如果我们有₁,bᵢ,…,bⱼ,一个₂与每个∈ S U 和 b ∈ U ∩和₁> ₂我们交换₁和₂, ₂,bᵢ,…,bⱼ,一个₁,反演计数较低。由于这种交换只重新排列S U的元素，而不是U∩S的元素，任何在U∩S上具有零反转的解和(在此前提下)在S U上具有最小反转数的解必须进行所有这样的交换。 因此:S U的元素必须顺序出现，因此解决方案是U∩S和S U的交错。