假设我的原始数据是
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
它已损坏，我只有一些不完整的集合，其中顺序有效但并非所有元素都存在。
1, 4, 6, 7, 8, 11, 12
1, 2, 4, 5, 6, 9, 10, 12
2, 4, 7, 9, 10, 11
4, 7, 9, 12
等等
我还有所有原始元素的列表，没有任何顺序。
我需要尽可能多地恢复原始数据。我不能保证我有足够的信息来恢复一切。我需要充分利用我所拥有的东西，并弄清楚哪些部分是可靠的。
可能会有并发症(但我会先解决没有它们的问题):
不完全集的顺序大部分是有效的，但可能会有一些错误，它是人写的。
对于不完整集合中的每对元素，我可能有额外的信息，例如
- “在 5 到 6 之间肯定没有任何东西”,
- “在 7 到 12 之间肯定还有其他东西，但我不确定具体有多少和什么”，
- “3 到 4 之间可能有也可能没有”,
- “在 7 到 9 之间恰好有一个未知项目”
我想将该信息合并到算法中以恢复更多数据。
到目前为止我最好的想法:
像这样在排序函数中使用不完整数组:如果存在 B 先于 A 的不完整集合，则得出 A > B 的结论。如果不存在同时存在 A 和 B 的集合，则返回 A == B .
我不喜欢的是我不知道哪些部分是完全恢复的，哪些是随机的。为了帮助我打乱原始元素列表，再次排序并查看哪些元素改变了位置，哪些没有改变。并这样做几千次(列表中的元素数量 < 50 所以我可以在这个问题上使用最推土机的方法)
有更好的建议吗？
最佳答案
从你的不完整集合构建有向图并制作topological sort
有些错误可能会被发现为循环(有向无环图中没有循环)
关于algorithm - 根据许多不完整的有序集恢复原始顺序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29869883/