作者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/cn.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