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