传递闭包和等价类

Question

我想问关于等价类中的传递闭包和排序问题。

我有一个布尔矩阵，我想要的结果是，从布尔矩阵，我计算传递闭包，找到等价类（es），并命令所有这些等价类（es）。

例如：我有一个曲线图

0 <-> 1 
     | 
     v 
     2 

我有2个等价类{{0; 1}; {2}}，并且对该类进行排序的结果是：{2}在类{0; 1}

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;; 

具有这些功能equivalence_classes和sort_equivalence_classes从测试：Asking about return type, list and set data structure in OCaml

我不明白，为什么功能eq输出和sort是相同的， 和这里两种功能的输出：[[3; 1; 0]; [1]];我不明白为什么它给了我这个结果，以及2在哪里？我怎么能得到我预期的结果？

非常感谢您

Answer 1

在您的示例transClo​​sure功能不改变矩阵。这对你的例子来说是正确的，但你应该用更多的输入来测试这个函数，以了解它是否有效。

一个错误是equivalence_class函数假定所有关系都是对称的，只检查一个方向。如果它看到i - > j它也假设为j - > i。 这不适用于您的数据，因此您会得到不正确的结果。您的矩阵示例具有0-> 1，2-> 0，2-> 1和2-> 3的关系。没有周期，所以不应该生成等价类。一旦你有循环，传递闭包应该将它们转换为自反对称子集。

另一个问题是你的关系不是自反的，但你需要反身性来获得单身等价集合。

所以为了得到这个工作，你需要1）使关系自反，2）修正equivalence_class函数来检查两个方向。