传递闭包与等价类
我想问一下等价类中的传递闭包和排序。
我有一个布尔矩阵，我想要的结果是，从布尔矩阵，我计算传递闭包，找到等价类，并对所有这些等价类进行排序。
例如:我有一个图表
0 <-> 1
|
v
2我有2个等价类{{0；1}；{2}}，这个类排序的结果是：{0；1}后的{2}
1)我想更多地了解为什么从传递闭包中我可以找到等价类？你能给我举个例子吗？通过例子我很容易理解。
2)下面是一个例子。我正在使用上面描述的算法进行测试。
let matrix =
[|[| false; true; false; false|];
[| false; false; false; false|];
[| true; true; false; true|];
[| false; false; false; false|];
|]
(* compute a transitive closure of a matrix *)
let transClosure matrix =
let n = Array.length matrix in
for k = 0 to n - 1 do
let mk = matrix.(k) in
for i = 0 to n - 1 do
let mi = matrix.(i) in
for j = 0 to n - 1 do
mi.(j) <- max mi.(j) (min mi.(k) mk.(j))
done;
done;
done;
matrix;;
(* compute transitive closure of boolean matrix *)
let tc_ma = transClosure matrix;;
(* compute equivalence classes on transitive closure*)
let eq = equivalence_classes tc_ma;;
(* sorting all equivalence classes *)
let sort = sort_equivalence_classes tc_ma eq;;使用来自：Asking about return type, list and set data structure in OCaml的equivalence_classes和sort_equivalence_classes函数
我不明白为什么函数eq和sort的输出是相同的，下面是这两个函数的输出：[[3; 1; 0]; [1]]；我不明白为什么它会给我这个结果，2在哪里？我怎样才能得到我期望的结果呢？
非常感谢
回答 1
Stack Overflow用户
发布于 2012-01-01 06:12:25
在您的示例中，transClosure函数不会更改矩阵。这对于您的示例是正确的，但您应该使用更多的输入来测试此函数，以了解它是否有效。
一个错误是equivalence_class函数假设所有关系都是对称的，并且只检查一个方向。如果它看到i和j，它也会假设j，->，i。你的数据不是这样的，所以你得到了不正确的结果。您的矩阵示例具有关系0->1，2->0，2->1和2->3。没有循环，因此不应生成等价类。一旦有了循环，传递闭包就应该将它们转换为自反对称子集。
另一个问题是你的关系不是自反性的，但是你需要自反性来获得单例等价集。
因此，要使其工作，您需要1)使关系是自反的，2)修复equivalence_class函数以检查两个方向。
https://stackoverflow.com/questions/8678948
复制相似问题
腾讯云开发者
