Just algorithm!
Circle




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



จบ




Create Date : 11 กรกฎาคม 2557
Last Update : 11 กรกฎาคม 2557 12:21:39 น. 1 comments
Counter : 440 Pageviews.

 
แบบว่าสมองทึบ แหะๆ แวะมาอวยพรวันเกิดอย่างเดียวแล้วกันค่า

คลิกๆๆ รูปสวยๆน่ารักๆไว้ส่งต่อเพียบ...


โดย: ประกายพรึก วันที่: 23 กรกฎาคม 2557 เวลา:23:34:37 น.  

ชื่อ :
Comment :
  *ใช้ code html ตกแต่งข้อความได้เฉพาะสมาชิก
 
รหัสส่งข้อความ
กรุณายืนยันรหัสส่งข้อความ

chaowman
Location :
กรุงเทพฯ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 8 คน [?]









New Comments
Group Blog
 
All Blogs
 
Friends' blogs
[Add chaowman's blog to your web]
Links
 

 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.