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

[expiate (彎曲屎殼郎)]

這是題目的網址：https://open.kattis.com/problems/bread
這題目的重點如下：

  - 三個相鄰的數字可以做旋轉，例如3,5,4 -> 4,3,5 -> 5,4,3
  - 大小為n的array裡面有n個相異的整數，其值為1,2,3,...,n
  - 給你一個起始的數列與最終的數列，回答可否藉由旋轉來完成轉換

EX1:
    n: 4
    起始：1 3 4 2
    最終：4 3 2 1

      1 3 4 2
    ->4 1 3 2
    ->4 2 1 3
    ->4 3 2 1 (Possible)

我在網路上搜尋到的解法是，對於 1 2 3 4這個數列，起始與最終轉換到1 2 3 4
是否滿足某個性質：
    對起始與最終數列，分別加總小於目前數值的個數，
    其相差如果是偶數則是 possible
    (如解釋不清楚，可以參照我下面的程式碼)


我對這演算法正確性的理解是
  - 相異的數，所以兩個數的關係不是小於就是大於
  - 計算小於的個數等同於計算大於的個數
  - 旋轉的關係會導致小於個數的變化
  - 當3個相鄰的數時，我們只要確定相差是2的倍數即可保證可轉換
  - 一般化來講，當k個相鄰的數時，是否要相差k-1的倍數才可保證能轉換?
    + 我是計算關係個數改變來做以上推斷

我比較沒有信心的部分是這種存在性，看似好像合理但我又不是很確定是否真的有
一系列的步驟可以完成這樣的轉換。也就是存在反例來打我臉XD
這邊不知道有沒有人可以理解我的擔憂?
我覺得好像還差一個步驟來完成這個一般化證明
先謝謝了


code:

    int count(vector<int> &arr, int idx, int n){
        int cnt=0;
        for(int i=idx+1;i<n;++i)
            if(arr[i]<arr[idx])
                ++cnt;

        return cnt;
    }

    int main(){
        int n;
        cin >> n;
        vector<int> org(n);
        vector<int> target(n);

        for(int i=0;i<n;++i) cin >> org[i];
        for(int i=0;i<n;++i) cin >> target[i];

        int res1=0,res2=0;
        for(int i=0;i<n;++i){
            res1 += count(org,i,n);
            res2 += count(target,i,n);
        }

        if(abs(res1-res2)%2==0)
            cout << "Possible" << endl;
        else
            cout << "Impossible" << endl;
      return 0;
    }

--
天下英雄出我輩，一入江湖歲月催。
鴻圖霸業談笑間，不勝人生一場醉。
提劍跨騎揮鬼雨，白骨如山鳥驚飛。
塵世如潮人如水，只嘆江湖幾人回。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 98.207.101.195 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1600823286.A.845.html
推 hwanger     : 你對symmetric group和alternative group熟嗎
→ expiate     : 抱歉，我連聽都沒聽過。是代數相關嗎?
→ hwanger     : 對 因為用這兩個概念 馬上就能驗證程式的正確性
→ hwanger     : 因為A_n是由3-cycle所生成的 所以只要考慮兩個
→ hwanger     : permutation的parity是否一樣就可以
→ hwanger     : 冏 我晚點再看看你是怎麼理解的好了
→ hwanger     : typo: alternating group
→ expiate     : 好的，請問有什麼參考資料是我可以開始的?
→ expiate     : 可以先出一些作業讓我先去理解我再跟你討論好了
→ hwanger     : 真的? 那先看下面網址(不用管normal subgroup)
→ hwanger     : https://reurl.cc/N605Ok
→ hwanger     : https://reurl.cc/Oqv2zy
→ hwanger     : 可以先不管證明 理解各個定義 引理 定理想講什麼就
→ hwanger     : 好了
→ expiate     : 好，我理解完會重新編輯我的文章再請你幫我看一下
推 hwanger     : 冏 沒辦法完全理解原PO想說的 很抱歉 然後 "- 一般
→ hwanger     : 化來講，當k個相鄰的數...">>這句話雖然我不是很理
→ hwanger     : 解 不過我想應該是沒有這個結論的 例如n=5時 考慮
→ hwanger     : Ok 我想錯了一些細節 不過應該就是沒那個結論
→ hwanger     : Ok 我補足了一些細節 當n=5 k=4 基本任兩種排列是可
→ hwanger     : 以互相轉換的 [因為<(1,2,3,4),(2,3,4,5)>=S_5]
→ hwanger     : 所以沒有那句話的結論 冏
→ hwanger     : 而[09/23 09:45]要改成A_n是由(1,2,3),(2,3,4),...,
→ hwanger     : (n-2,n-1,n)所生成的
→ hwanger     : 更進一步 隨便一個n 考慮k=4 也就是我們可以讓任意
→ hwanger     : 相鄰四個做循環的話 則我們想要怎麼排就可以怎麼排
→ hwanger     : [因為<(1,2,3,4),...,(n-3,n-2,n-1,n)> = S_n]
→ expiate     : 謝謝你的幫忙，那我先學習完你給我的教材我再另外發
→ expiate     : 文章請教你好了