algorithm - 合并具有未知排序函数的数据

Question

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

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

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

例子:

A B D
A C D

无法正确排序，无法决定B和C的顺序

A B D
A B C
A C D

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

Answer 1

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

我将用你的例子来解释:

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

现在您需要填充矩阵，遍历每个输入数组并获取每个字符及其后的字符。使用这 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 个位置，因为当一个字符小于另一个字符时，也意味着第二个字符大于第一个字符。

现在您只需一次将字符插入一个数组(链表是最简单的，稍后您会明白为什么)

每次插入 char 时，您将从返回数组的开头开始，遍历，查找第一个数组中的索引，并检查矩阵中的 Type.Greater 或 Type.Less(取决于在比较的方式上，curr char 到 array，或 array 到 current char)并在遇到与预期不同的值时插入它。

如果您在插入期间在矩阵中点击了 Type.Unknown，您知道您没有足够的信息来对这些数组进行排序，如果您点击了 Type.Equal，则可以忽略插入此字符(假设您不不想在你的结果中重复。)

然后你会输出你的返回数组