關於循環置換

Question

我學過數學，我想出了這個問題。 有兩個排列A和B和一個整數M. 如果我們可以從A到B做下面的操作，我們說A幾乎等於B.
-1選擇排列的M長度段A.
-2在其上向右執行循環移位（因此，如果子段爲「1 2 3 4 5」（m = 5），則在此操作之後，它將是「5 1 2 3 4」。）

問：A幾乎等於B嗎？

我認爲這是典型的，但我找不到答案。 如何解決呢？（未蠻力！）

數置換元素< = 10^5

例如

A 「1 2 3」
B 「2 3 1」
m = 2的
回答YES
解釋 「1 2 3」 - > 「2 1 3」 - > 「2 3 1」

Answer 1

這是我的綴的證明ecture。假設n是排列的長度，m是我們允許旋轉的窗口的長度，其中1 ≤ m ≤ n。如果存在將P轉換爲Q的窗口旋轉序列，則排列P和Q是幾乎相等。幾乎相等是一個等價關係。以下是關於等價類的聲明。

(1) m = 1: P almost equals Q if and only if P = Q 
(2) m = n: P almost equals Q if and only if they're rotations of each other 
(3) 1 < m < n, m odd: P almost equals Q if and only if they have the same parity 
(4) 1 < m < n, n even: P almost equals Q 

前兩個索賠是顯而易見的。至於(3)，奇偶條件的必要性來自旋轉奇數長度的窗口是偶數排列的事實。

這裏爭論的肉找到時n = m + 1 ≥ 4的算法，因爲在一般情況下，我們可以使用類似於插入排序算法進行改造P讓所有，但最後m + 1元素匹配Q，並且具體而言，案件(n, m) = (3, 2)可以通過檢查來解決。在m爲偶數的情況下，我們進一步確保轉換匹配Q的奇偶性，如果必要的話將最後的m元素旋轉一次。 （對於m奇數，我們只是假設等於奇偶校驗。）

我們需要一種技術來一次移動少於m的元素。假設狀態如下。

1, 2, 3, 4, ..., m, m + 1 

旋轉第二個窗口m - 1（即一次反向）。

1, 3, 4, ..., m, m + 1, 2 

旋轉第一個窗口m - 1次。

3, 4, ..., m, m + 1, 1, 2 

二，兩次。

3, 2, 4, ..., m, m + 1, 1 
3, 1, 2, 4, ..., m, m + 1 

我們成功地旋轉了前三個元素。這足以結合通過旋轉到「插入排序」Q的第一個m - 1元件到位。另外兩個按照正確的順序排列。