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