algorithm - 关于循环排列

Question

我学的是数学，我想出了这个问题。有两个排列 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

例子

一个“1 2 3”
B "2 3 1"
米=2
回答‖是的
说明『1 2 3"->"2 1 3"->"2 3 1"

Answer 1

这里证明了我的猜想。设 n 是排列的长度，m 是允许旋转的窗口的长度，其中 1 ≤ m ≤ n .如果存在将 P 转换为 的窗口旋转序列，则 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 元素“插入排序”到位的结合结合。其他两个在奇偶匹配中顺序正确。