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

看板Math作者 (彎曲屎殼郎)時間5年前 (2020/09/24 03:04), 編輯推噓0(0推 0噓 77→)
留言77則, 2人參與, 5年前最新討論串2/3 (看更多)
我讀了李華介老師的大學基礎代數講義的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://www.ptt.cc/bbs/Math/M.1600887869.A.5EA.html
→
09/24 07:18, 5年前 , 1F
parity就是指even和odd這兩個性質
09/24 07:18, 1F
→
09/24 07:24, 5年前 , 2F
接著我們需要引入另一個重要的定理: 所有的even
09/24 07:24, 2F
→
09/24 07:26, 5年前 , 3F
permutation都可以用(1 2 3),(2 3 4),...,
09/24 07:26, 3F
→
09/24 07:28, 5年前 , 4F
(n-2 n-1 n)的乘積來表示 也就是給定一個even
09/24 07:28, 4F
→
09/24 07:31, 5年前 , 5F
permutation σ 則σ=(τ1)(τ2)...(τk) 其中(τi)
09/24 07:31, 5F
→
09/24 07:35, 5年前 , 6F
在{(1 2 3),(2 3 4),...,(n-2 n-1 n)} (可以重覆選
09/24 07:35, 6F
→
09/24 07:36, 5年前 , 7F
取 也就是(τ1),...,(τk)有可能不相異)
09/24 07:36, 7F
→
09/24 07:39, 5年前 , 8F
/**********這是分隔線 我們該要有的都有了*******/
09/24 07:39, 8F
→
09/24 07:42, 5年前 , 9F
給一個entries為1到n並相異的array a[1],a[2],...,
09/24 07:42, 9F
→
09/24 07:44, 5年前 , 10F
a[n] (注意下標從1開始 方便討論) 則我們有一個自然
09/24 07:44, 10F
→
09/24 07:48, 5年前 , 11F
而然的permutation σ 就是σ(i)=a[i] σ將i送到在
09/24 07:48, 11F
→
09/24 07:48, 5年前 , 12F
第i個位置上的數字
09/24 07:48, 12F
→
09/24 07:55, 5年前 , 13F
那"對三個相鄰的數字做旋轉"就對應到σ乘上
09/24 07:55, 13F
→
09/24 07:58, 5年前 , 14F
(k k+1 k+2)^{-1}=(k k+1 k+2)^2=(k+2 k+1 k)
09/24 07:58, 14F
→
09/24 08:00, 5年前 , 15F
譬如說 我們現在想要將第1位置上的數字放到第2位置
09/24 08:00, 15F
→
09/24 08:02, 5年前 , 16F
第2位置的數字放到第3位置上 第3的放到第1位置上 則
09/24 08:02, 16F
→
09/24 08:04, 5年前 , 17F
做完後的array對應到的permutation就是σ(3 2 1)
09/24 08:04, 17F
→
09/24 08:08, 5年前 , 18F
因為(σ(3 2 1))(1)=σ(3),(σ(3 2 1))(2)=σ(1),
09/24 08:08, 18F
→
09/24 08:08, 5年前 , 19F
(σ(3 2 1))(3)=σ(2), (σ(3 2 1))(m)=σ(m)當m不
09/24 08:08, 19F
→
09/24 08:09, 5年前 , 20F
是1,2,3時
09/24 08:09, 20F
→
09/24 08:15, 5年前 , 21F
/*************基本的對應在此結束***************/
09/24 08:15, 21F
→
09/24 08:24, 5年前 , 22F
令Q為{(1 2 3),(2 3 4),...,(n-2 n-1 n)}這個集合
09/24 08:24, 22F
→
09/24 08:26, 5年前 , 23F
給兩個arrays其對應到的permutations為σ,ρ 則原本
09/24 08:26, 23F
→
09/24 08:28, 5年前 , 24F
麵包轉轉轉的問題就等價於是否存在(τ1),(τ2),...,
09/24 08:28, 24F
→
09/24 08:29, 5年前 , 25F
(τk)在Q中 使得σ(τ1)^{-1}...(τk)^{-1}=ρ 移項
09/24 08:29, 25F
→
09/24 08:33, 5年前 , 26F
一下得σρ^{-1}=(τ1)...(τk)^{-1} 綜合一下所有
09/24 08:33, 26F
→
09/24 08:33, 5年前 , 27F
的觀念 我們得到第一個小結論: 這兩個arrays可以互
09/24 08:33, 27F
→
09/24 08:34, 5年前 , 28F
相轉換 若且唯若 σρ^{-1}是even permutation
09/24 08:34, 28F
→
09/24 08:37, 5年前 , 29F
這裡值得注意的是ρ和ρ^{-1}是具有相同parity的
09/24 08:37, 29F
→
09/24 08:38, 5年前 , 30F
所以我們迎來我們第二個小結論: σρ^{-1}是even 若
09/24 08:38, 30F
→
09/24 08:39, 5年前 , 31F
且唯若 σ和ρ同是even或同是odd
09/24 08:39, 31F
→
09/24 08:41, 5年前 , 32F
最後我們得到我們真正需要的結論: 這兩個arrays可以
09/24 08:41, 32F
→
09/24 08:42, 5年前 , 33F
互相轉換 若且唯若 σ和ρ同是even或同是odd
09/24 08:42, 33F
→
09/24 08:45, 5年前 , 34F
/*********看似漫長 實則一瞬的理論結束了********/
09/24 08:45, 34F
→
09/24 09:02, 5年前 , 35F
接下來的問題就是: 給定一個array (vector<int>)a
09/24 09:02, 35F
→
09/24 09:03, 5年前 , 36F
我們要如何計算a相應到的permutation的parity
09/24 09:03, 36F
→
09/24 09:05, 5年前 , 37F
而前一篇的程式的思路很簡單 如果我們一次只做"任意
09/24 09:05, 37F
→
09/24 09:07, 5年前 , 38F
兩個相鄰位置的互換"(對應到transposition 也就是
09/24 09:07, 38F
→
09/24 09:10, 5年前 , 39F
2-cycle) 那我們就去計算要做多少次 我們可以讓a變
09/24 09:10, 39F
→
09/24 09:12, 5年前 , 40F
成 vector<int> I={1,2,...,n};
09/24 09:12, 40F
→
09/24 09:16, 5年前 , 41F
/*********概念有了 看看程式具體的作法**********/
09/24 09:16, 41F
→
09/24 09:21, 5年前 , 42F
先考慮count(a,n-2,n) 他要嘛是0 要嘛是1
09/24 09:21, 42F
→
09/24 09:22, 5年前 , 43F
如果是0 代表a的最後兩個位置已經排序好了
09/24 09:22, 43F
→
09/24 09:24, 5年前 , 44F
如果是1 則我們需要對換最後兩個 以得到一個array b
09/24 09:24, 44F
→
09/24 09:26, 5年前 , 45F
使得b的最後兩個位置已經排序好了
09/24 09:26, 45F
→
09/24 09:28, 5年前 , 46F
如此繼續 假設c是從a得到的一個array 使得c[0]=a[0]
09/24 09:28, 46F
→
09/24 09:29, 5年前 , 47F
c[1]=a[1],...,c[i]=a[i] 而c[i+1]之後的entries是
09/24 09:29, 47F
→
09/24 09:30, 5年前 , 48F
a[i+1]之後的entries的排序結果
09/24 09:30, 48F
→
09/24 09:33, 5年前 , 49F
這裡我們會有count(a,i,n)=count(c,i,n) 這是因為
09/24 09:33, 49F
→
09/24 09:35, 5年前 , 50F
c[i]=a[i] 而a[i+1]之後的entries和c[i+1]之後的
09/24 09:35, 50F
→
09/24 09:35, 5年前 , 51F
entries是一樣的
09/24 09:35, 51F
→
09/24 09:38, 5年前 , 52F
此時 如果我們做"count(a,i,n)次"的"兩個相鄰位置互
09/24 09:38, 52F
→
09/24 09:39, 5年前 , 53F
換" 則我們可以將c[i]調到"所有在c[i+1]之後 比c[i]
09/24 09:39, 53F
→
09/24 09:40, 5年前 , 54F
小的entries" 的後方 而我們也會同時得到一個新的
09/24 09:40, 54F
→
09/24 09:42, 5年前 , 55F
array d使得d[0]=a[0],d[1]=a[1],...,d[i-1]=a[i-1]
09/24 09:42, 55F
→
09/24 09:44, 5年前 , 56F
而d[i]之後的entries是a[i]之後的entries的排序
09/24 09:44, 56F
→
09/24 09:49, 5年前 , 57F
就這樣 在做了"res_a=count(a,0,n)+count(a,1,n)+..
09/24 09:49, 57F
→
09/24 09:50, 5年前 , 58F
count(a,n-1,n)"次的"兩個相鄰位置的互換"後 我們就
09/24 09:50, 58F
→
09/24 09:52, 5年前 , 59F
將a給排序好了 意即我們得到了最終的array I
09/24 09:52, 59F
→
09/24 09:54, 5年前 , 60F
/**************最難的部份已經過去了************/
09/24 09:54, 60F
→
09/24 09:57, 5年前 , 61F
此時 對應到a的permutation的奇偶性就是res_a的奇偶
09/24 09:57, 61F
→
09/24 10:00, 5年前 , 62F
性 所以程式中res1和res2的奇偶性就是org和target所
09/24 10:00, 62F
→
09/24 10:01, 5年前 , 63F
對應到的permutation的奇偶性
09/24 10:01, 63F
→
09/24 10:03, 5年前 , 64F
所以我們只需要檢驗res1和res2是否同奇或同偶就行了
09/24 10:03, 64F
→
09/24 10:04, 5年前 , 65F
這就是整個程式的邏輯 以及程式正確性的證明...
09/24 10:04, 65F
→
09/24 10:16, 5年前 , 66F
/********以下是針對原文中的問題一些回應********/
09/24 10:16, 66F
→
09/24 10:17, 5年前 , 67F
"對三個相鄰的數字做旋轉可以...">>>的確就是理解成
09/24 10:17, 67F
→
09/24 10:17, 5年前 , 68F
這樣
09/24 10:17, 68F
→
09/24 10:18, 5年前 , 69F
"對於breadsorting問題...">>>在上述過程中 我們並
09/24 10:18, 69F
→
09/24 10:19, 5年前 , 70F
不需要disjoint cycle decomposition的概念 所以沒
09/24 10:19, 70F
→
09/24 10:19, 5年前 , 71F
差
09/24 10:19, 71F
→
09/24 10:22, 5年前 , 72F
"感謝你分享的教材...">>>我只是google "alternatin
09/24 10:22, 72F
→
09/24 10:23, 5年前 , 73F
g group"找到的 會想給你 就是他寫的異常簡潔 但該
09/24 10:23, 73F
→
09/24 10:23, 5年前 , 74F
有的 我們要用到的 他都有了
09/24 10:23, 74F
→
09/24 11:35, 5年前 , 75F
感謝大大詳細的解說，我先消化一下再向你請教不懂的
09/24 11:35, 75F
→
09/24 11:35, 5年前 , 76F
地方。再次感謝你的幫忙
09/24 11:35, 76F
→
09/24 14:05, 5年前 , 77F
也可以順便看看T大的回文
09/24 14:05, 77F
‣ 更多 expiate 的文章
文章代碼(AID): #1VQvmzNg (Math)
‣ 更多 expiate 的文章
文章代碼(AID): #1VQvmzNg (Math)