合并具有未知排序功能的数据

Question

我有许多字符串数组。根据相同的标准，每个数组中的字符串都以相同的方式排序。但是，某些数组可能缺少某些字符串，并且可能没有包含完整字符串的数组。此外，用于比较字符串的标准不适用于我：在数组上下文之外，我无法确定哪个字符串应该在另一个字符串的前面。

我需要一种方法来生成一组完整的字符串，正确排序。或者当阵列没有足够的信息让我这么做时失败。

有人熟悉这类问题吗？什么是适当的算法？

例子：

A B D 
A C D 

不能正确排序，不能决定B的顺序和C

A B D 
A B C 
A C D 

这有足够的信息来正确排序ABCD。

Answer 1

这听起来像是topological sorting问题的特例。

Answer 2

你会有多少套？的东西，如果他们不是太稀疏可能的工作是：

1. 遍历所有 计数每个 串是多么常见的数组的第一个元素。
2. 选择哪个元素是最常见的 。
3. 检查所有字符串的所有 数组的每个元素。
4. 如果在比所述第一阵列的以外的任何元素存在， 其父阵列的第一个元素被选择并且转到步骤3.
5. 从所有阵列的 第一个元素中删除所选元件/树木 并将其添加到输出 列表的末尾。
6. 转到1，直到所有元素都被删除，删除 。

如果将阵列转储到b-trees中，元素搜索可能会非常快。您也可以通过播放数组的顺序来进一步加速第3步。我仍然在想那个。

如果数组非常稀疏，我唯一能想到的就是使用某种有监督的机器学习来尝试确定正确的排序方法。

Answer 3

这与典型的diff/merge algorithm有什么不同？只要这两个数组都是“排序”的，无论它们被排序的机制如何。他们被相互排序，所以你应该能够使用相似性来合并差异。之后，它基本上是任意的。

如果您想将[A]与[B，C，D]合并，那么您不知道A会走向哪里（前端？结束？在C和D之间？您不知道）。在这些情况下，你只需要提出一个约定（总是在前面，总是在末尾，类似的东西）。如果您想要[Q，X，Y，A，B]与[Q，X，W，B，D]合并，您需要确定“W”是在前面还是后面“Y，A”。所以，[Q，X，Y，A，W，B，D]是正确的还是[Q，X，W，Y，A，B，D]是正确的。坦率地说，你只需要打个电话就可以随身携带。根本没有足够的信息。

Answer 4

部分解决方案：

您需要确定排序。你可以通过询问你的数据来“投票”一个符号在另一个符号之前的次数。您将需要一个大小等于符号数量的方阵。初始化为全零，然后扫描所有输入字符串，为每个连续对（a，b）加上M（a，b）。然后，你需要清理这些数据，所以你得到一个可传递的顺序（如果A在B之前，C在C之前，A也必须在C之前）。为此，您需要遍历不同符号的所有三元组，并“协调”不相等的三元组，因此它们尊重传递性。

如果您的数据不是太嘈杂，这应该只需要一次。如果数据过于嘈杂，则可能需要运行多遍才能收敛，或者采用一些贪婪的方法：而不是以随机顺序遍历所有符号，按照递减数量的顺序遍历所有不相等的三元组。

Answer 5

一种可能的方式我能想到的，虽然可能不是最有效的：

我就要用你的例子来解释：

A B D 
A B C 
A C D 

创造的独特的字符数组，所以你将得到（举例）：

A B D C 

而且你应该有一个枚举来形容可能关系

enum Type 
{ 
    Unknown = 0, 
    Greater = 1, 
    Equal = 2, 
    Less = 3, 
} 

现在，创建一个尺寸与上述数组相同的方形矩阵，默认情况下所有对象都是Type.Unknown。

0 0 0 0 
0 0 0 0 
0 0 0 0 
0 0 0 0 

当您计算排序时，您的数组将作为矩阵的索引。要明白我的意思，看看这里：

A B D C 
A 0 0 0 0 
B 0 0 0 0 
D 0 0 0 0 
C 0 0 0 0 

去通过，使对角线为Type.Equal

2 0 0 0 
0 2 0 0 
0 0 2 0 
0 0 0 2 

现在，您需要填充矩阵，遍历每个输入数组，并得到每个字符和后面的一个。使用这两个字符，找到每个矩阵中的索引（使用数组）并更新矩阵。

for(int i=0; i<len(arr)-1; i++) 
{ 
    char c1 = arr[i], c2 = arr[i+1]; 
    int i1,i2; 
    //get indices of characters in array and put in i1, and i2 respectively 
    matrix[i1][i2] = Type.Less; 
    matrix[i2][i1] = Type.Greater 
} 

分配在网格每次2个位置，因为当一个字符是小于另一个，这也意味着所述第二字符是大于第一。

现在您只需一次插入的字符到一个数组一个（链表是最简单的，你就会明白为什么在第二）

每次插入字符，你将开始在开始你的返回数组，然后迭代，查找第一个数组中的索引，并检查矩阵中的Type.Greater或Type.Less（取决于你正在比较的方式，curr char到数组还是数组当前字符）并插入它，如果你遇到一个不同于你所期望的值。

如果你在插入过程中在matix中打了一个Type.Unknown，你知道你没有足够的信息对这些数组进行排序，如果你点击了Type.Equal，你可以忽略插入这个字符串（假设你不用“不想在你的结果重复。）

然后您可以输出你的回报阵列

Answer 6

的主要问题是，鉴于一些数据，你需要确定排序功能。之后，它只是列表排序。

生成所有数组的第一个元素列表。删除重复项。所以这个：

A B 
A C 
B C 
C C 
C D 

变成（A，B，C）。然后，我们需要一组表示我们知道的每个值都小于其他值的对。 （（A，B），（A，C），（B，C））。

现在，我们可以在数组的开头找到每个值，将所有以该值开始的数组作为一个组。删除其第一个元素。这就使我们：

B 
C 

，

C 

和

C 
D 

递归每个阵列的这些名单。

一旦我们完成了对所有子集的递归，我们将生成的对合并到最初创建的对中。我们应该以（（A，B），（A，C），（B，C），（C，D））结束。 （A，B），（A，C），（A，D），（B，C），（B，D），（C，D） ）。

你现在少于功能只是看看它的比较值是否在这个集合中。如果是这样，没错。否则，错误。

Answer 7

1）ort数据。如果部分排序不一致，则会出现循环，并且tsort将失败。否则，你有一个序列s（0）... s（n-1）。 2）对于每对s（i），s（i + 1），在部分序列中搜索彼此相邻的同一对。如果你在其中一个中找到它，那么继续下一个我。如果你没有找到它，那么失败，因为部分序列不排序s（i）和s（i + 1）。

为什么不呢？因为如果他们确实订购了它们，但它们并不相邻，那么它们之间肯定存在某种东西。但是如果他们之间在部分序列之间存在某种东西，但是没有以全部序列出现，那么该入侵者必须以全部序列在s（i）之前或s（i + 1）之后。这与完整序列与已经证明的部分序列的一致性相矛盾。

步骤2是O（n * m），其中n是要排序的元素的数量，m是所有部分序列的总长度。你可能可以做得更好，但这很简单，因为你可以从第1步获取tsort，第2步是一堆明显的嵌套循环。请注意，如果找到s（i）（或s（i + 1）），则可以停止搜索每个部分序列，因为它肯定不会再发生。

Answer 8

Doug McClean获胜。进入我脑海的这句话是分层的，这导致了网络搜索中的死胡同。 （例如，在逻辑程序设计中，说到分层程序是很有用的;这些程序是可以形象化为一堆图层的程序，每一层都包含一个或多个谓词，每个谓词都是扩展（底层）或以下只能从它下面的层中的谓词中获得，理想情况下需要这种形式，其中每个层最多只有一个字符串）。

您的toposort算法的变体会让您构建一个DAG（您暗示非循环得到保证），也许可以随时跟踪具有零输入边缘的节点（简单优化）。如果完成后，你有多个“根”节点，那么你就完成了，因为你知道你没有第一个节点。否则，你只有一个;从DAG中删除它，检查它的每个子节点现在是否是“根”节点;并继续前进，直到获得多个根节点（失败）或者节点用完（成功）。

上面所勾画的算法在字符串数量上应该是线性的（基本上是两次迭代）。如果每个节点有许多孩子，这可以说是与字符串数量的平方成正比，这意味着每个字符串在列表列表中出现很多次，每个字符串紧接着它们都有不同的字符串。

Answer 9

我很想说为了获得足够的信息来完成合并，最终合并数组中相邻的每一对x，y必须位于输入数组中的某处。换句话说，传递性可能根本不会出现在图片中。有人可以产生一个反例吗？

如果你愿意，你可以在答案的这里做。

Answer 10

一个简单的递归例程怎么样？

使用你的第二个例子：

A B D 
A B C 
A C D 

创建所有的唯一排序的哈希表：

table = {A -> B, C 
     B -> C, D 
     C -> D} 

数了所有的独特的价值观

countUnique = 4 

的使用堆栈，计算所有可能的路径。当堆栈长度匹配唯一字符串的数量时，您知道您有解决方案。如果您找到多个解决方案，那么您在某处有循环引用。 请原谅我可疑的伪代码。

main() 
{ 
    foreach (s in table.keys) 
    { 
    stack.push(s) 
    searchForPath() 
    stack.pop() 
    } 
} 

searchForPath() 
{ 
    if (table.hasKey(stack.peek)) 
    { 
    // we're not at the end yet 
    foreach (s in table[stack.peek]) 
    { 
     // avoid infinite recursion 
     if (stack.contains(s) 
     continue 

     stack.push(s) 
     searchForPath() 
     stack.pop() 
    } 
    } 
    else 
    { 
    if (stack.size == countUnique) 
    { 
     // solution found 
     captureSolution() 
    } 
    } 
}