โจทย์ข้อนี้ให้หาจำนวนรูปแบบของวงกลม
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)
จบ