โจทย์ข้อนี้ให้หาจำนวนรูปแบบของวงกลม Hamiltonion Cycle

สมมติ วงกลมเรียงตามจุดหมายเลข 1-2-3-4-5 (และต่อจาก 5 คือ 1 ใหม่)

กับวงกลมตามหมายเลข 2-3-4-5-1 เป็นวงกลมชุดเดียวกัน เพราะเรียงเหมือนวงกลมแรก แค่เริ่มจาก 2 เท่านั้นเอง

และวงกลม 5-4-3-2-1 ก็ถือเป็นวงกลมชุดเดียวกัน เพราะไม่ว่าจะเรียงจากหน้าไปหลัง หรือหลังไปหน้า ก็เรียงเหมือนกัน

แต่กับวงกลม 1-3-2-4-5 ถือเป็นวงกลมคนละชุด เพราะเรียงไม่เหมือนกัน



ยังไม่จบ โจทย์มีข้อห้ามให้บางจุด ไม่สามารถเชื่อมกัน

เช่น ห้าม 3-5

เราไม่สามารถสร้างรูปแบบ 1-2-3-5-4 ได้

โจทย์จะให้จำนวนของจุด และจุดที่ห้ามเชื่อมกัน แล้วให้หาจำนวนชุดของวงกลมทั้งหมด

โดยคำตอบต้อง modulo กับ 99010

อ่านเพิ่มเติม ที่นี่



เนื่องจากเรามี constraint ที่ห้ามบางจุดเชื่อมกัน เราจึงไม่สามารถใช้ factorial คำนวนได้

แต่ถ้าเรา loop ทดลองทีละวิธี วิธีนี้อาจจะมีความซับซ้อนถึง O(n!) (n สามารถมีค่าถึง 300)

แต่โจทย์บอกว่า จุดที่ห้ามเชื่อมกันจะมีไม่เกิน 15 ชุด

ดังนั้น เราอาจใช้ factorial หาจำนวนวิธีการเรียงของวงกลม ทำให้ได้จำนวนรูปแบบของวงกลมทั้งหมด

แล้วค่อยหาจำนวนรูปแบบที่มีจุดที่ห้ามเชื่อมกัน แล้วเอามาลบกัน



เริ่มจาก class ช่วยก่อน

type EdgeString = { terminal:string Set; connections:string Set }
module Edge =
    let TryJoin b a =
        let conn = Set.intersect a.terminal b.terminal
        if conn = Set.empty
        then None
        else Some({ terminal = a.terminal + b.terminal - conn; 
                    connections = a.connections + b.connections + conn })

เหตุผลที่มี class นี้เพราะ เราจะเอาไว้หาจุดเชื่อม

เช่น EdgeString 1-2-3 terminal คือปลายของเส้น คือ 1;3 ส่วน connections คือจุดกลางของเส้น คือ 2

คำสั่ง TryJoin คือลองเชื่อม EdgeString 2 เส้นดู เช่น 1-2-3 เชื่อมกับ 3-4-5 จะกลายเป็น 1-2-3-4-5



ถัดมา อีกคำสั่งที่จำเป็นเลย คือ factorial

let rec fac n =
    if n <= 1 
    then 1
    else n * fac (n-1) % 99010

เราสามารถ % 99010 ได้เลย เพราะโจทย์กำหนด มิเช่นนั้นอาจจะ overflow



เริ่ม solve กันเลย

let solve len set =

len คือ จำนวนจุด

set คือ set ของจุดที่ห้ามเชื่อมกัน



ถัดมาคือ หาวิธีเรียงทั้งหมด

let allCount = fac (len-1) / 2

สมมติ จำนวนจุดทั้งหมดคือ 5

วิธีการเรียงทั้งหมดคือ (n-1)!/2

n-1 เพราะตามหลักด้านบน 1-2-3-4-5 และ 2-3-4-5-1 คือวงกลมเดียวกัน

และ /2 เพราะตามหลักด้านบนเช่นเดียวกัน 1-2-3-4-5 และ 5-4-3-2-1 คือวงกลมเดียวกัน

ดังนั้น รูปแบบวงกลมทั้งหมดมี


(5-1)!/2 = 12 รูปแบบ



ถัดมาเป็นคำสั่งยาวหน่อย

let rec combin id = function
    | 0   -> Seq.singleton List.empty
    | cnt -> let collectFn i =
                let edge = Array.get set i
                let Validate it =
                    Set.intersect it.connections edge.terminal = Set.empty &&
                    (Set.count it.connections = len-2 || it.terminal <> edge.terminal)
                seq {
                    for edges in combin (i+1) (cnt-1) do
                    if Seq.forall Validate edges then
                    let foldFn (edge,list) it =
                        match Edge.TryJoin edge it with
                        | None          -> edge,it::list
                        | Some(newEdge) -> newEdge,list
                    let newEdge,list = Seq.fold foldFn (edge,List.empty) edges
                    yield newEdge::list
                }
             let finish = Array.length set - cnt
             Seq.collect collectFn {id..finish}

คำสั่งยาว แต่ไม่มีอะไรมาก มันคือคำสั่งลองเชื่อมจุดแบบต่างๆ ดู

เช่น ถ้ามี 1-2, 2-3, และ 3-4

มันก็จะได้ [1-2-3] [1-2;3-4] [2-3-4]



ถัดมา อันนี้ซับซ้อนนิดนึง

let forbidCount = 
    let sumFn i =
        let sign = if i % 2 = 0 then -1 else 1
        let allCount = fac (len-i-1) % 9901
        let sumFnX edges =
            let len = List.length edges
            Seq.fold (fun last i -> last * 2 % 9901) 1 {2..len} % 9901
        let combCount = combin 0 i |> Seq.sumBy sumFnX
        sign * allCount * combCount % 9901
    let maxCombo = min (Array.length set) len
    Seq.sumBy sumFn {1..maxCombo} % 9901

คำสั่งชุดนี้ ไว้หาว่า รูปแบบวงกลมที่มีจุดที่ห้ามเชื่อมกัน มีกี่รูปแบบ

คำสั่งนี้ ใช้หลักการ Inclusion-Exclusion Principle

เช่น ถ้าห้าม 1-2, 2-3 และ 3-4

จะมี set ทั้งหมด 7 set คือ [1-2] [2-3] [3-4] [1-2-3] [1-2;3-4] [2-3-4] [1-2-3-4]

ถ้าเข้าตามสูตรด้านบนจะได้ดังนี้

จำนวน Union	Set	จำนวนรูปแบบทั้งหมด
1	[1-2]	6
	[2-3]	6
	[3-4]	6
2	[1-2-3]	-2
	[1-2;3-4]	-4
	[2-3-4]	-2
3	[1-2-3-4]	1

รวมกัน แบบที่มีจุดที่ห้ามเชื่อมกันทั้งหมด คือ 11 รูปแบบ

สุดท้ายเอามาหักลบกัน

let count = allCount - forbidCount
string ((count+9901) % 9901)

เช่น จากด้านบน ถ้าจำนวนจุดคือ 5 และห้าม 1-2, 2-3, และ 3-4

allCount คือ 12

forbitCount คือ 11

คำตอบคือ 1 (เส้น 1-3-5-2-4)



จบ