根据许多不完整的有序集恢复原始顺序
Restore the original order based on many incomplete ordered sets
假设我的原始数据是
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都存在的集合return A == B.
我不喜欢的是我不知道哪些部分是完全恢复的，哪些是随机的。为了帮助我打乱原始元素列表，再次排序并查看哪些元素改变了位置，哪些没有改变。并重复几千次（列表中的元素数 < 50 所以我可以在这个问题上使用最推土机的方法）
有更好的建议吗？
从你的不完整集合构建有向图并使 topological sort
有些错误可能会被发现为循环（有向无环图中没有循环）
我想如果你拿一个最长的字符串并尝试通过两个 neithebor 符号（也包括开始和结束）将这个字符串与所有其他字符串进行比较，我想一些算法可以是这样的：如果在其他字符串中它之间有一些东西，添加这个到最长的字符串，然后重新开始。如果没有要添加的，请检查下一对。
按照 MBo 的建议构建有向图。如果生成的图是有向无环图 (DAG)，则视为对原始数据的验证，并且可以执行拓扑排序以恢复有关原始顺序的信息。
如果您认为您的所有信息都是可靠的，可以将一些附加信息合并到图表中。例如，"there is certainly nothing between 5 and 6" 表示（如果理解为 5 -> 6）图中从 v 到 6（v 不等于 5）的每条边都可以用从 v 到 5 的边代替。 "There may or may not be anything between 3 and 4"：这一切告诉我们的是 3 -> 4，如果它说的那么多的话。
其他信息比较难用。 "Something between 7 and 12" 可以作为 7 -> 12 合并到有向图中，但 "something" 部分不能，据我所知。可能有一种方法可以通过扩大图形以包含 "something" 个顶点来使用它，但我无法让它工作。相反，我建议让您的顶级算法吐出每个顶级排序（前提是没有太多）并根据它们符合多少附加约束来评估它们。作为奖励，您会发现有多少种不同的答案是可能的。您也可以在排序时使用它，例如，如果您正在寻找 7 之后立即出现的项目，请不要选择 12，但这对我来说感觉很乱，如果信息自相矛盾。
如果生成的图不是 DAG，您仍然可以将它分成强连通的组件（例如，Tarjan 的算法）。强连通分量是不可靠的部分。强连通组件本身将形成一个可以进行topsorted的DAG，但每个大于1个顶点的组件都需要进一步特殊处理。解决这个问题的一种方法是尝试找到一个 最小反馈弧集 ，即在强连接组件中消除边的最小数量，以将其转换为 DAG。最小反馈弧集问题是NP-hard，但是问题是"fixed-parameter tractable":http://dl.acm.org/citation.cfm?doid=1411509.1411511。不太合理的方法也可能会起作用，例如识别循环并删除循环中的随机边缘，直到没有更多循环。
假设我的原始数据是
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都存在的集合return A == B.
我不喜欢的是我不知道哪些部分是完全恢复的，哪些是随机的。为了帮助我打乱原始元素列表，再次排序并查看哪些元素改变了位置，哪些没有改变。并重复几千次（列表中的元素数 < 50 所以我可以在这个问题上使用最推土机的方法）
有更好的建议吗？
从你的不完整集合构建有向图并使 topological sort
有些错误可能会被发现为循环（有向无环图中没有循环）
我想如果你拿一个最长的字符串并尝试通过两个 neithebor 符号（也包括开始和结束）将这个字符串与所有其他字符串进行比较，我想一些算法可以是这样的：如果在其他字符串中它之间有一些东西，添加这个到最长的字符串，然后重新开始。如果没有要添加的，请检查下一对。
按照 MBo 的建议构建有向图。如果生成的图是有向无环图 (DAG)，则视为对原始数据的验证，并且可以执行拓扑排序以恢复有关原始顺序的信息。
如果您认为您的所有信息都是可靠的，可以将一些附加信息合并到图表中。例如，"there is certainly nothing between 5 and 6" 表示（如果理解为 5 -> 6）图中从 v 到 6（v 不等于 5）的每条边都可以用从 v 到 5 的边代替。 "There may or may not be anything between 3 and 4"：这一切告诉我们的是 3 -> 4，如果它说的那么多的话。
其他信息比较难用。 "Something between 7 and 12" 可以作为 7 -> 12 合并到有向图中，但 "something" 部分不能，据我所知。可能有一种方法可以通过扩大图形以包含 "something" 个顶点来使用它，但我无法让它工作。相反，我建议让您的顶级算法吐出每个顶级排序（前提是没有太多）并根据它们符合多少附加约束来评估它们。作为奖励，您会发现有多少种不同的答案是可能的。您也可以在排序时使用它，例如，如果您正在寻找 7 之后立即出现的项目，请不要选择 12，但这对我来说感觉很乱，如果信息自相矛盾。
如果生成的图不是 DAG，您仍然可以将它分成强连通的组件（例如，Tarjan 的算法）。强连通分量是不可靠的部分。强连通组件本身将形成一个可以进行topsorted的DAG，但每个大于1个顶点的组件都需要进一步特殊处理。解决这个问题的一种方法是尝试找到一个 最小反馈弧集 ，即在强连接组件中消除边的最小数量，以将其转换为 DAG。最小反馈弧集问题是NP-hard，但是问题是"fixed-parameter tractable":http://dl.acm.org/citation.cfm?doid=1411509.1411511。不太合理的方法也可能会起作用，例如识别循环并删除循环中的随机边缘，直到没有更多循环。