zhuangzhuang · December 16, 2022 09:23 · Dec 16, 2022
diff --git a/country_colour.fsx b/country_colour.fsx
@@ -0,0 +1,51 @@
+// 简单图作色
+type Country = string
+type Map = (Country * Country) list
+
+type Colour = Country list
+type Colouring = Colour list
+
+
+let rec isMember x =
+    function
+    | y :: ys -> x = y || (isMember x ys)
+    | [] -> false
+
+
+let areNb (m: Map) c1 c2 =
+    isMember (c1, c2) m || isMember (c2, c1) m
+
+let rec canBeExtBy (m: Map) (col: Colour) c =
+    match col with
+    | [] -> true
+    | c' :: col' -> not (areNb m c' c) && canBeExtBy m col' c
+
+let rec extColouring (m: Map) (cols: Colouring) c =
+    match cols with
+    | [] -> [ [ c ] ]
+    | col :: cols' ->
+        if canBeExtBy m col c then
+            (c :: col) :: cols'
+        else
+            col :: extColouring m cols' c
+
+let addElem x ys = if isMember x ys then ys else x :: ys
+// 收集所有城市名称
+let rec countries =
+    function
+    | [] -> []
+    | (c1, c2) :: m -> addElem c1 (addElem c2 (countries m))
+
+let rec colCntrs (m: Map) =
+    function
+    | [] -> []
+    | c :: cs -> extColouring m (colCntrs m cs) c
+
+let colMap (m: Map) : Colouring = colCntrs m (countries m)
+
+// 地图邻居表
+let exMap = [ ("a", "b"); ("c", "d"); ("d", "a") ]
+
+let res = colMap exMap
+
+printfn "Map: %A\nColouring: %A" exMap res