关于循环置换
我学习了数学，然后想到了这个问题。有两个排列A和B和一个整数M。如果我们可以使A到B执行以下操作，则说A几乎等于B。
-1选择置换A的M长度片段。
-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
回答是
解释“ 1 2 3”->“ 2 1 3”->“ 2 3 1”
回答：
这是我的猜想的证明。让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)，奇偶条件的必要性源于以下事实：旋转奇数长度的窗口是偶数排列。
这里争论的重点是找到一个when的算法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, 13, 1, 2, 4, ..., m, m + 1
我们已经成功地旋转了前三个元素。这与旋转共轭相结合就足以将“插入”的第一个m - 1元素“放置” Q到位。其他两个按奇偶校验顺序排列正确。
以上是 关于循环置换 的全部内容， 来源链接： utcz.com/qa/403202.html
