validation和规范化部分有序集
我有一对像这样的对：
[["a", "b"], ["b", "d"], ["a", "c"], ["e", "d"], ["a", "d"], ..., ["s", "f"]] -
检查给定数组是否可以表示部分排序的有效方法是什么？ 也就是说，给定数组中没有“循环”，如
["a", "b"], ["b", "c"], ["c", "a"]。 -
如果确认数组表示偏序，我想通过去除所有可以通过自反性或传递性导出的对来对其进行标准化。 例如，在上文中，由于存在
["a", "b"]和["b", "d"]，所以该对["a", "d"]是多余的，应该被移除。
1到2之间的顺序无关紧要。 如果2应该在1的过程之前或之内完成，那么，这很好。
我最好在Ruby 1.9.3中使用它，但只需伪代码即可。
对于1号：
您可以将问题模块化为图形 ，并且每对都是边缘，接下来您可以运行拓扑排序 – 如果算法失败，图形不是DAG – 并且存在“循环” – 否则 – 您得到一个可能的部分顺序，作为拓扑排序的输出。
对于number2：
我根本不确定这个部分，所以这个答案实际上只是部分的，抱歉 – 但只是一个初步的：
您可以使用DFS ，并将“已发现”顶点中的边删除到[刚刚发现的顶点] [在同一路径上]。 虽然我认为它不是最优的，但是可能会反复进行[直到没有做出任何改变]才会改进它。
更深入的数字2：
我不确定你的意思，但是DFS创建的森林满足了你的要求，但是我担心你可能会丢失过多的数据，例如： ["a","b"],["a","c"],["b",d"],["c","d"]将修剪["b","d"]或["c","d"] ，这可能是太多了，但它也会修剪所有“冗余”边缘，如示例中所述。
第二个问题被称为传递减少 。
对于问题的第一部分，我在数学网站的答案帮助下得出了我自己的答案。
对于问题的第二部分，在遵循其他答案中给出的建议后，我在Ruby（i） Floyd-Warshall算法中实现了计算传递闭包，（ii）组成，以及（iii）使用公式R的传递减少^ – = R – R \ cdot R ^ +。
module Digraph; module_function def vertices graph; graph.flatten(1).uniq end ## Floyd-Warshall algorithm def transitive_closure graph vs = vertices(graph) path = graph.inject({}){|path, e| path[e] = true; path} vs.each{|k| vs.each{|i| vs.each{|j| path[[i, j]] ||= true if path[[i, k]] && path[[k, j]]}}} path.keys end def compose graph1, graph2 vs = (vertices(graph1) + vertices(graph2)).uniq path1 = graph1.inject({}){|path, e| path[e] = true; path} path2 = graph2.inject({}){|path, e| path[e] = true; path} path = {} vs.each{|k| vs.each{|i| vs.each{|j| path[[i, j]] ||= true if path1[[i, k]] && path2[[k, j]]}}} path.keys end def transitive_reduction graph graph - compose(graph, transitive_closure(graph)) end end
用法示例：
Digraph.transitive_closure([[1, 2], [2, 3], [3, 4]]) #=> [[1, 2], [2, 3], [3, 4], [1, 3], [1, 4], [2, 4]] Digraph.compose([[1, 2], [2, 3]], [[2, 4], [3, 5]]) #=> [[1, 4], [2, 5]] Digraph.transitive_reduction([[1, 2], [2, 3], [3, 4], [1, 3], [1, 4], [2, 4]]) #=> [[1, 2], [2, 3], [3, 4]]