Created
December 16, 2022 09:23
-
-
Save zhuangzhuang/5db01bc2415a9cced6a463f78a75ed5b to your computer and use it in GitHub Desktop.
简单图作色
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // 简单图作色 | |
| 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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment