使用Union-Find获取等价类

Question

我有一个简单的联合代码-如下所示：

let rec find p x =
      if p.(x) = x
      then x
      else
        let y = find p (p.(x)) in
        p.(x) <- y;
        y;;       
let union x y p =
  p.(find p y) <- p.(find p x);
  p

示例：

let a = [|0;1;2;3;4|]

let print_array a =
 Array.iter (fun i -> Printf.printf "%i" i; print_string " ") a

let print_union =
  let a = union 0 1 a in
  print_string "Result union (0, 1): ";
  print_array a;
  print_string "\n"

其结果将是：

Result union (0, 1): 0 0 2 3 4 

我很难走得更远，以获得不相交的一套。例如，我想要得到的上面的示例：{0,1},{2},{3},{4}

谢谢你的帮助。

Answer 1

由于明显的原因，如果不遍历整个结构，就无法打印结果。

所以，你想从你所有的工会收集居民--找到：

let print_classes a =
 (* Let's first create an array for storing the classes *)
 let classes = Array.make (Array.length a) [] in

 (* Let's now populate it!
    I'm going backwards in the array to have nicer printing *)
 for i = (Array.length classes) - 1 downto 0
 do classes.(a.(i)) <- i :: (classes.(a.(i))) done;

 (* And now the printing *)
 Array.iter (function
   | [] -> ()
   | h::t -> Printf.printf "{%d%a}" h
             (fun c -> List.iter (fun x -> Printf.fprintf c ",%i" x)) t
   )
   classes

为了简洁起见，我使用Printf函数，您可以找到它们的doc 这里。

请注意，这可能会得到改进，因为它创建了一个可能“几乎没有”填充的大数组。根据使用此函数的频率，您可能希望与类领导一起存储等效类(我必须这样做一次，我使用了stdlib中的Set和Map )。