作者TimcApple (肥鵝)
看板Math
標題Re: [其他] 特殊排序(breadsorting)的理解與一般化
時間Thu Sep 24 11:40:57 2020
來說明一下第一篇的演算法用了什麼
(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://webptt.com/m.aspx?n=bbs/Math/M.1600918859.A.0D3.html
1F：推 hwanger : inversion sequence想了一整天 想不起這個名詞 冏 09/24 13:52
2F：→ hwanger : 簡單無腦倒不至於啦 XD 不過最常被拿來用是真的 畢 09/24 13:54
3F：→ hwanger : 竟每本離散的書都有教 這道程式題剛好用到不少的 09/24 13:58
4F：→ hwanger : symmetric group的知識 才會讓人覺得為什麼要用 09/24 13:59
5F：→ hwanger : inversion number來算parity 09/24 14:01
6F：推 expiate : 感謝大大的解說，對h大沒有冒犯，不過這篇需要的知 09/25 04:42
7F：→ expiate : 識比較少比較好懂。抱歉我離散也不熟，如果是很基 09/25 04:42
8F：→ expiate : 本問題可以直接給我連結，耽誤大家時間了 09/25 04:42
9F：→ hwanger : XD e大能懂就好了 不過這篇需要的知識沒有比較少 冏 09/25 08:27
10F：→ hwanger : 我只是嚴格定義了 "排列L 和S_n在收集所有排列L的集 09/25 08:29
11F：→ hwanger : 合上的action" 以及用不同的方式證了"inversion 09/25 08:30
12F：→ hwanger : number的parity就是permutation的parity"這件事 09/25 08:31
13F：→ hwanger : 原題目也不是很基本的題目啦 XD 為了證程式的正確性 09/25 08:44
14F：→ hwanger : permutation的parity一定要用某種形式被定義 (雖然 09/25 08:47
15F：→ hwanger : 這是大學代數的基本知識 但在比較基礎的書中 也幾乎 09/25 08:48
16F：→ hwanger : 只有大學代數會講這個 冏) 09/25 08:50
17F：→ hwanger : 至於inversion sequence 因其是algorithm of 09/25 08:54
18F：→ hwanger : generating permutations的副產品 所以變成在離散的 09/25 08:55
19F：→ hwanger : 書上通常都看得到 而會做這種程式題目的通常都有一 09/25 08:57
20F：→ hwanger : 定程度的離散知識 所以才會使得inversion number變 09/25 08:59
21F：→ hwanger : 成基本技巧 09/25 08:59