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

[TimcApple (肥鵝)]

來說明一下第一篇的演算法用了什麼

(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
推 hwanger     : inversion sequence想了一整天 想不起這個名詞 冏
→ hwanger     : 簡單無腦倒不至於啦 XD 不過最常被拿來用是真的 畢
→ hwanger     : 竟每本離散的書都有教 這道程式題剛好用到不少的
→ hwanger     : symmetric group的知識 才會讓人覺得為什麼要用
→ hwanger     : inversion number來算parity
推 expiate     : 感謝大大的解說，對h大沒有冒犯，不過這篇需要的知
→ expiate     : 識比較少比較好懂。抱歉我離散也不熟，如果是很基
→ expiate     : 本問題可以直接給我連結，耽誤大家時間了
→ hwanger     : XD e大能懂就好了 不過這篇需要的知識沒有比較少 冏
→ hwanger     : 我只是嚴格定義了 "排列L 和S_n在收集所有排列L的集
→ hwanger     : 合上的action" 以及用不同的方式證了"inversion
→ hwanger     : number的parity就是permutation的parity"這件事
→ hwanger     : 原題目也不是很基本的題目啦 XD 為了證程式的正確性
→ hwanger     : permutation的parity一定要用某種形式被定義 (雖然
→ hwanger     : 這是大學代數的基本知識 但在比較基礎的書中 也幾乎
→ hwanger     : 只有大學代數會講這個 冏)
→ hwanger     : 至於inversion sequence 因其是algorithm of
→ hwanger     : generating permutations的副產品 所以變成在離散的
→ hwanger     : 書上通常都看得到 而會做這種程式題目的通常都有一
→ hwanger     : 定程度的離散知識 所以才會使得inversion number變
→ hwanger     : 成基本技巧