F＃中的并查集

Question

关于F#中可用的数据结构
是否有任何“官方”的实现不相交集数据结构，例如Union-Find的实现？

我在谷歌上找到的唯一信息是这些代码片段：

带路径压缩的加权快速联合

请注意，我是F#和编程的初学者。
有什么高效的替代方案吗？

- Fagui Curtain

Answer 1

F# 数据结构

关于 F# 可用的数据结构，是否有“官方”的不相交集数据结构实现，例如 Union Find 的实现？

我不知道是否有官方版本。

F# 数据结构最著名的来源：

• F# 集合类型
• FSharpx.Collections

曾经有 F# PowerPack，它是一个包含大量有用代码的文件，但现在已被分解成部分。

请查看Jack Fox 的文章了解有关 F# 数据结构的重要信息。

对于特定领域的数据结构，请搜索F# 社区项目。

特别是对于 Union/Find：

在实用逻辑和自动推理手册中的lib.ml中，John Harrison定义了equate和canonize。

在lib.fs的F#翻译中，它们仍然是equate和canonize。

并且在翻译过程中的注释中提到：

请参见：不相交集合数据结构
请参见：自动推理中的主题 - 第5讲 - 第4页：并查集

union被称为equate。
find被称为canonize。

还有哪些高效的替代方法？

我不知道John Harrison的代码是否更高效，因为我没有运行过任何测试。我也不知道是否有其他实现，但我知道该版本可以很好地作为自动定理证明器核心的一部分。

- Guy Coder

Answer 2

我已经自己实现了这个功能，它并不难。我希望它没有 bug。 < p >< code >UnionFind.fs

// union find by rank with path compression

namespace UnionFind


// using array from 1..N 
// don't use .[0]

type Node = { Parent:int ; Rank:int}

type Partition (N:int) = 

    let nodearray =   [| for i in 0..N do yield {Parent = i; Rank = 0} |]

    let length = (Array.length nodearray) - 1

    member p.Item 
        with get(idx) = nodearray.[idx]

    member p.find (i) = 
        let mutable tmp0 = i
        let mutable tmp1 = p.[i].Parent
        while (tmp0 <> tmp1) do tmp0 <- tmp1
                                tmp1 <- p.[tmp1].Parent
        tmp0
    member p.find_compress (i) :int =
        let mutable tmp0 = i
        let mutable tmp1 = p.[i].Parent
        let rec one_step ok list =
            match ok with 
              | false -> list
              | true ->   tmp0 <- tmp1
                          tmp1 <- p.[tmp1].Parent
                          one_step (tmp0<>tmp1) (tmp0::list) 

        let list = one_step (tmp0<>tmp1) [i]  
        // ranks stay the same with find_compress
        list |> List.head |> (fun i ->  let r = nodearray.[i].Rank
                                        (nodearray.[i] <- {Parent = tmp0 ; Rank=r} ))
        list |> List.tail |> List.iter ( fun i -> let r = nodearray.[i].Rank
                                                  (nodearray.[i] <- {Parent = tmp0 ; Rank=r} ))

        tmp0

    member p.union_by_rank (i,j) : bool = // returns false if i and j hav the same parent, true otherwise
       if i=j then false else
          let x = p.find_compress(i)
          let y = p.find_compress(j)
          let rx = p.[x].Rank 
          let ry = p.[y].Rank

          if x=y then false else
             if (rx<ry) then nodearray.[x] <- {Parent = y; Rank = rx}                         
             if (ry<rx) then nodearray.[y] <- {Parent = x; Rank = ry}                
             if (rx=ry) then nodearray.[x] <- {Parent = y; Rank = ry}
                             nodearray.[y] <- {Parent = y; Rank = ry+1}
             true                             

    member p.print() = 
       printfn "%A" nodearray

    member p.output() = [|for i in 0..length do yield (i,p.find_compress(i))|]

- Fagui Curtain