合并两个部分（联合超定）套订购信息 [英] Merging two partial (jointly overdetermined) sets of ordering information

问题描述

我有一个网格数据的Web应用程序。用户可重新排序的列，并且服务器可以改变所存在的列。我想保存用户的列的顺序在cookie中，并在页面加载恢复它。

I have a web app with data in a grid. The user can reorder the columns, and the server can change which columns exist. I would like to save the user's column order in a cookie and restore it on page load.

更正式地说，我有一个唯一的ID（字符串）两列名为 user_columns 和 server_columns 。我想重新排列 server_columns 这样的，我尊敬的所有的从 user_columns 订购信息，并尽可能多的 server_columns 越好。我该怎么做呢？什么是对尽可能合理的正式定义？

More formally, I have two arrays of unique IDs (strings) called user_columns and server_columns. I would like to reorder server_columns such that I respect all of the ordering information from user_columns, and as much from server_columns as possible. How do I do this? What's a reasonable formal definition of "as much as possible"?

我的分析至今：

这个问题的一个方面很简单：如果服务器中删除某些列，从 user_columns 删除相应的条目。哪些不再有列的顺序的任何信息都是没有实际意义。这个问题就变成了合并两个潜在冲突的套订购信息之一。

One aspect of the problem is trivial: if the server removes some columns, delete the corresponding entries from user_columns. Any information about the ordering of columns which are no longer there is moot. The problem then becomes one of merging two potentially conflicting sets of ordering information.

这相当于一个家庭可以投票理论问题：给定一组空格，每一个都包含了候选人之间的部分订单，生产在某种意义上反映出选票的候选人一完整的订购

This corresponds to a family of problems from voting theory: given a set of ballots, each of which contains a partial order between the candidates, produce a complete ordering of the candidates which in some sense reflects the ballots.

这使我觉得我可能会得到一个可行的解决方案通过将如在舒尔茨方法或的排行双来投票的基础上 user_columns 和 server_columns 。对于UX的原因，在去年将新列（右侧），打破关系似乎是一个不错的主意，我。

This leads me to think that I might get a workable solution by applying e.g. the Schulze Method or Ranked Pairs to a sufficiently rigged set of ballots based on user_columns and server_columns. For UX reasons, breaking ties by inserting new columns last (to the right) seems like a good idea to me.

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

Does this sound like it's on the right track?

还要注意的是，我们可以考虑三种类型的比较：A和B都在 user_columns ，其中之一是，或者他们都不是。前者和后者的种类是很容易解决（参见 user_columns 和 server_columns ，分别）;一个在中间，并与后者的相互作用，是棘手的部分

Note also that we can consider three kinds of comparisons: A and B are both in user_columns, one of them is, or none of them are. The former and latter kinds are easily resolved (refer to user_columns and server_columns, respectively); the one in the middle, and its interactions with the latter, are the tricky parts.

推荐答案

比方说，我们的 C 的列，从 1 的编号为 C 的。我们列的两个序列序列的 U = U <子> 1 ，U ₂ ，... U <子> N 的和取值= S <子> 1 ，S ₂ ，内容S <子> M 的。我们希望找到一个置换的 P 的的的取值的，这样的 P 的没有倒方面的 U 的和倒置的关于最小数量的取值的。

Let's say we have C columns, numbered from 1 to C. We have two sequences sequences of columns, U = u₁, u₂, ... u_n and S = s₁, s₂, ... s_m. We want to find a permutation P of S, such that P has no inversions with regard to U and a minimal number of inversions with regard to S.

我们可以证明，有这样一个最优的 P 的是对的 U的∩小号的交织和取值\ U 的。所谓交错我的意思是 P 的没有倒方面的 U的∩小号或取值\ U 的。

We can show that there is such an optimal P which is an interleaving of U ∩ S and S \ U. By "interleaving" I mean that P has no inversions with regard to U ∩ S or S \ U.

我们可以将动态规划，以找到最佳的交织：设A =（A <子>我）= U∩S和B =（B <子>Ĵ）= S \ U.令的 F（I，J）的是倒WRT数取值的的$ P $的最佳交织pfixes一个<子> 1 ...我 B的A和B的<子> 1 ...，J 这个想法是非常相似的最长公共子 DP算法。我们有复发

We can apply dynamic programming to find the optimal interleaving: Let A = (a_i) = U ∩ S and B = (b_j) = S \ U. Let f(i,j) be the number of inversions w.r.t. S of the optimal interleaving of the prefixes a_1...i of A and b_1...j of B. The idea is very similar to the longest common subsequence DP algorithm. We have the recurrence

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，如果X] 在这里表示值 1 ，如果X是真实的， 0 ，如果X是假的。

I used the notation [1 if X] here to denote the value 1, if X is true and 0, if X is false.

矩阵 F 可建在时间O（| A | ^ 2 * | B | ^ 2）。最小成本（倒WRT的S号），将 F（| A |，| B |）的。

The matrix f can be built in time O(|A|^2 * |B|^2). The minimal cost (number of inversions w.r.t. S) will be f(|A|, |B|).

我们可以使用DP矩阵以及重建的最优排列：我们从后到前建立它。我们先从元组（I，J）=（| A |，| B |），并在这取决于两个选项是最小的DP过渡，我们知道我们是否需要把A [1]或每一步乙[j]的向排列的前面。然后我们进行第（i-1，j）的或（I，J-1），这取决于我们选择

We can reconstruct the optimal permutation using the DP matrix as well: We build it from back to front. We start with the tuple (i,j) = (|A|, |B|) and at every step depending on which of the two options is minimum in the DP transition, we know whether we need to put A[i] or B[j] to the front of the permutation. Then we proceed with (i-1, j) or (i, j-1) depending on which we choose.

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

Here is an implementation of the algorithm, please excuse my lack of JS skills.

这篇关于合并两个部分（联合超定）套订购信息的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！