Re: [其他] 特殊排序(breadsorting)的理解與一般化

看板Math作者TimcApple (肥鵝)時間5年前 (2020/09/24 11:40)推噓2(2推 0噓 19→)

留言21則, 2人參與討論串3/3 (看更多)

來說明一下第一篇的演算法用了什麼 (Def) 給定 1~n 的排列 L 稱 inversion = sum 每個數前面有幾個數比它大 ex: [1 5 2 4 3] 1: 沒有 5: 沒有 2: 5 4: 5 3: 5 4 inversion of [1 5 2 4 3] = 4 (Def) 一個排列 L 的 inversion 為 even 或 odd 則稱 L 為 even 或 odd ex: [1 5 2 4 3] 是 even, 因為 4 是偶數 (Lem 1) 設 c 為 2-cycle, L 為 1~n 排列若 L 是 even (odd), 則 cL 是 odd (even) (pf) 設 c = (i j), 即 i j 位置交換若 j = i + 1, 由 inversion 定義可知恰好差 1 個對任意 2-cycle 都能拆成奇數個相鄰形 2-cycle ex: (14) = (12)(23)(34)(23)(12) (Thm 2) 設 L 為 1~n 排列, L0 = [1 2 ... n] 從 L 開始，透過 k 次 2-cycle 變回 L0 若 L 是 even (odd), 則 k 也是 even (odd) (注意 k 不是固定值，只能確定奇偶) (pf) L0 的 inversion 是 0, 因此 L0 是 even 上一個定理表示每次 2-cycle, inversion 的奇偶都要跳一次那就很明顯了，想從偶數到偶數，跳奇數次是不可能的嘛 (Def) 設 p in Sym(n), L0 = [1 2 ... n] 稱 p 為 even (odd), 若 p L0 是 even (odd) (Thm 3) 若 p 為 even (odd) 則 p 為 even (odd) 個 2-cycle 的 composition (pf) Thm 2 重寫一次 (Coro) 所有 2-cycle 都是 odd (pf) 因為是 1 個 2-cycle 的 composition (Thm 4) p q 是 even 或 odd, 取決於 p 和 q 的 (pf) 都用 Thm 2 就對了，inversion 最好做 (Prop 5) (123) 是 even, (i i+1 i+2) 也是 (pf) (123) = (13)(12), odd + odd = even (Thm 6) 所有 even p in Sym(n), (n > 2) 都是 (123), (234), ..., (n-2 n-1 n) 的 composition (pf) 考慮從 p L0 變成 L0, 只能用上面那些 cycle 首先把 n 換到最後一個再把 n-1 換到倒數第二個以此類推，直到把 3 換成第三個現在前兩個位置只能是 [1 2 或 [2 1 可是如果是 [2 1 就違反了 Thm 2, 結束把這些 even p 裝起來的集合就是 Alt(n) Thm 6 的證明提供了一個暴力法用程式直接驗證 p 是 even 或 odd 可是無論是數學證明或跑程式 inversion 都是最簡單無腦的作法ow o -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.19.130 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1600918859.A.0D3.html

推