作者expiate (弯曲屎壳郎)
看板Math
标题Re: [其他] 特殊排序(breadsorting)的理解与一般化
时间Thu Sep 24 03:04:25 2020
我读了李华介老师的大学基础代数讲义的3.4部分，
但是我没去理解证明只接受定理的结论
以下是我目前理解的部分：
- Sn: the symmetric group of degree n
+ 从 {1,2,...,n} 到 {1,2,...,n}所有1-1且onto的函数所成的集合
- Sn可以用disjoint cycle decomposition表示
- 属於Sn的cycle都可以分解成2-cycle的乘积(函数合成)
+ k-cycle可以写成k-1个2-cycle的乘积
+ if k-cycle is even, k is "odd"
+ if k-cycle is odd, k is "even"
- 若a,b同为even permutation或同为odd permutation，则a。b为even permutation
- 若a,b一个为even permutation，另一个为odd permutation，
则a。b为odd permutation
基於上述我理解的部分，我该怎麽应用在breadsorting上呢?
- 对三个相邻的数字做旋转可以理解成3-cycle，所以可以用两个2-cycle表示
- 对於breadsorting问题，是不是不能用disjoint cycle decomposition表示?
例如{1,2,3,4}中，(1,2,3)是3-cycle但是(2,3,4)也是3-cycle但是他们并不是
disjoint
- 请问你说的parity具体是指什麽呢？与我之前想的小於个数有关系吗？
感谢你分享的教材，虽然我没学过代数，但至少还能从中了解一些概念
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 98.207.101.195 (美国)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1600887869.A.5EA.html
1F：→ hwanger : parity就是指even和odd这两个性质 09/24 07:18
2F：→ hwanger : 接着我们需要引入另一个重要的定理: 所有的even 09/24 07:24
3F：→ hwanger : permutation都可以用(1 2 3),(2 3 4),..., 09/24 07:26
4F：→ hwanger : (n-2 n-1 n)的乘积来表示 也就是给定一个even 09/24 07:28
5F：→ hwanger : permutation σ 则σ=(τ1)(τ2)...(τk) 其中(τi) 09/24 07:31
6F：→ hwanger : 在{(1 2 3),(2 3 4),...,(n-2 n-1 n)} (可以重覆选 09/24 07:35
7F：→ hwanger : 取 也就是(τ1),...,(τk)有可能不相异) 09/24 07:36
8F：→ hwanger : /**********这是分隔线 我们该要有的都有了*******/ 09/24 07:39
9F：→ hwanger : 给一个entries为1到n并相异的array a[1],a[2],..., 09/24 07:42
10F：→ hwanger : a[n] (注意下标从1开始 方便讨论) 则我们有一个自然 09/24 07:44
11F：→ hwanger : 而然的permutation σ 就是σ(i)=a[i] σ将i送到在 09/24 07:48
12F：→ hwanger : 第i个位置上的数字 09/24 07:48
13F：→ hwanger : 那"对三个相邻的数字做旋转"就对应到σ乘上 09/24 07:55
14F：→ hwanger : (k k+1 k+2)^{-1}=(k k+1 k+2)^2=(k+2 k+1 k) 09/24 07:58
15F：→ hwanger : 譬如说 我们现在想要将第1位置上的数字放到第2位置 09/24 08:00
16F：→ hwanger : 第2位置的数字放到第3位置上 第3的放到第1位置上 则 09/24 08:02
17F：→ hwanger : 做完後的array对应到的permutation就是σ(3 2 1) 09/24 08:04
18F：→ hwanger : 因为(σ(3 2 1))(1)=σ(3),(σ(3 2 1))(2)=σ(1), 09/24 08:08
19F：→ hwanger : (σ(3 2 1))(3)=σ(2), (σ(3 2 1))(m)=σ(m)当m不 09/24 08:08
20F：→ hwanger : 是1,2,3时 09/24 08:09
21F：→ hwanger : /*************基本的对应在此结束***************/ 09/24 08:15
22F：→ hwanger : 令Q为{(1 2 3),(2 3 4),...,(n-2 n-1 n)}这个集合 09/24 08:24
23F：→ hwanger : 给两个arrays其对应到的permutations为σ,ρ 则原本 09/24 08:26
24F：→ hwanger : 面包转转转的问题就等价於是否存在(τ1),(τ2),..., 09/24 08:28
25F：→ hwanger : (τk)在Q中 使得σ(τ1)^{-1}...(τk)^{-1}=ρ 移项 09/24 08:29
26F：→ hwanger : 一下得σρ^{-1}=(τ1)...(τk)^{-1} 综合一下所有 09/24 08:33
27F：→ hwanger : 的观念 我们得到第一个小结论: 这两个arrays可以互 09/24 08:33
28F：→ hwanger : 相转换 若且唯若 σρ^{-1}是even permutation 09/24 08:34
29F：→ hwanger : 这里值得注意的是ρ和ρ^{-1}是具有相同parity的 09/24 08:37
30F：→ hwanger : 所以我们迎来我们第二个小结论: σρ^{-1}是even 若 09/24 08:38
31F：→ hwanger : 且唯若 σ和ρ同是even或同是odd 09/24 08:39
32F：→ hwanger : 最後我们得到我们真正需要的结论: 这两个arrays可以 09/24 08:41
33F：→ hwanger : 互相转换 若且唯若 σ和ρ同是even或同是odd 09/24 08:42
34F：→ hwanger : /*********看似漫长 实则一瞬的理论结束了********/ 09/24 08:45
35F：→ hwanger : 接下来的问题就是: 给定一个array (vector<int>)a 09/24 09:02
36F：→ hwanger : 我们要如何计算a相应到的permutation的parity 09/24 09:03
37F：→ hwanger : 而前一篇的程式的思路很简单 如果我们一次只做"任意 09/24 09:05
38F：→ hwanger : 两个相邻位置的互换"(对应到transposition 也就是 09/24 09:07
39F：→ hwanger : 2-cycle) 那我们就去计算要做多少次 我们可以让a变 09/24 09:10
40F：→ hwanger : 成 vector<int> I={1,2,...,n}; 09/24 09:12
41F：→ hwanger : /*********概念有了 看看程式具体的作法**********/ 09/24 09:16
42F：→ hwanger : 先考虑count(a,n-2,n) 他要嘛是0 要嘛是1 09/24 09:21
43F：→ hwanger : 如果是0 代表a的最後两个位置已经排序好了 09/24 09:22
44F：→ hwanger : 如果是1 则我们需要对换最後两个 以得到一个array b 09/24 09:24
45F：→ hwanger : 使得b的最後两个位置已经排序好了 09/24 09:26
46F：→ hwanger : 如此继续 假设c是从a得到的一个array 使得c[0]=a[0] 09/24 09:28
47F：→ hwanger : c[1]=a[1],...,c[i]=a[i] 而c[i+1]之後的entries是 09/24 09:29
48F：→ hwanger : a[i+1]之後的entries的排序结果 09/24 09:30
49F：→ hwanger : 这里我们会有count(a,i,n)=count(c,i,n) 这是因为 09/24 09:33
50F：→ hwanger : c[i]=a[i] 而a[i+1]之後的entries和c[i+1]之後的 09/24 09:35
51F：→ hwanger : entries是一样的 09/24 09:35
52F：→ hwanger : 此时 如果我们做"count(a,i,n)次"的"两个相邻位置互 09/24 09:38
53F：→ hwanger : 换" 则我们可以将c[i]调到"所有在c[i+1]之後 比c[i] 09/24 09:39
54F：→ hwanger : 小的entries" 的後方 而我们也会同时得到一个新的 09/24 09:40
55F：→ hwanger : array d使得d[0]=a[0],d[1]=a[1],...,d[i-1]=a[i-1] 09/24 09:42
56F：→ hwanger : 而d[i]之後的entries是a[i]之後的entries的排序 09/24 09:44
57F：→ hwanger : 就这样 在做了"res_a=count(a,0,n)+count(a,1,n)+.. 09/24 09:49
58F：→ hwanger : count(a,n-1,n)"次的"两个相邻位置的互换"後 我们就 09/24 09:50
59F：→ hwanger : 将a给排序好了 意即我们得到了最终的array I 09/24 09:52
60F：→ hwanger : /**************最难的部份已经过去了************/ 09/24 09:54
61F：→ hwanger : 此时 对应到a的permutation的奇偶性就是res_a的奇偶 09/24 09:57
62F：→ hwanger : 性 所以程式中res1和res2的奇偶性就是org和target所 09/24 10:00
63F：→ hwanger : 对应到的permutation的奇偶性 09/24 10:01
64F：→ hwanger : 所以我们只需要检验res1和res2是否同奇或同偶就行了 09/24 10:03
65F：→ hwanger : 这就是整个程式的逻辑 以及程式正确性的证明... 09/24 10:04
66F：→ hwanger : /********以下是针对原文中的问题一些回应********/ 09/24 10:16
67F：→ hwanger : "对三个相邻的数字做旋转可以...">>>的确就是理解成 09/24 10:17
68F：→ hwanger : 这样 09/24 10:17
69F：→ hwanger : "对於breadsorting问题...">>>在上述过程中 我们并 09/24 10:18
70F：→ hwanger : 不需要disjoint cycle decomposition的概念 所以没 09/24 10:19
71F：→ hwanger : 差 09/24 10:19
72F：→ hwanger : "感谢你分享的教材...">>>我只是google "alternatin 09/24 10:22
73F：→ hwanger : g group"找到的 会想给你 就是他写的异常简洁 但该 09/24 10:23
74F：→ hwanger : 有的 我们要用到的 他都有了 09/24 10:23
75F：→ expiate : 感谢大大详细的解说，我先消化一下再向你请教不懂的 09/24 11:35
76F：→ expiate : 地方。再次感谢你的帮忙 09/24 11:35
77F：→ hwanger : 也可以顺便看看T大的回文 09/24 14:05