关于循环排列
About Cyclic Permutation
我是学数学的，想出了这个问题。
有两个排列 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”
m=2
回答‖是
说明『1 2 3"->"2 1 3"->"2 3 1"
证明我的猜想。设 n 为排列的长度，m 为允许旋转的 windows 的长度，其中 1 ≤ m ≤ n。排列 P 和 Q 几乎相等 如果存在 window 旋转序列将 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)，奇偶条件的必要性是因为奇数长度的window旋转是偶数排列。
这里争论的重点是找到一个算法n = m + 1 ≥ 4，因为一般情况下，我们可以使用类似于插入排序的算法来转换P，使得除了最后一个m + 1个元素匹配Q，具体情况(n, m) = (3, 2)可以通过检查解决。如果 m 是偶数，我们进一步确保转换与 Q 的奇偶性匹配，如有必要，通过旋转最后的 m 元素一次。 （对于 m 奇数，我们假设平价。）
我们需要一种技术来一次移动少于 m 个元素。假设状态如下
1, 2, 3, 4, ..., m, m + 1
旋转第二个 window m - 1 次（即反向一次）。
1, 3, 4, ..., m, m + 1, 2
旋转第 window 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 元素到位的 "insertion sort" 共轭。其他两个按奇偶校验顺序正确。
我是学数学的，想出了这个问题。
有两个排列 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”
m=2
回答‖是
说明『1 2 3"->"2 1 3"->"2 3 1"
证明我的猜想。设 n 为排列的长度，m 为允许旋转的 windows 的长度，其中 1 ≤ m ≤ n。排列 P 和 Q 几乎相等 如果存在 window 旋转序列将 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)，奇偶条件的必要性是因为奇数长度的window旋转是偶数排列。
这里争论的重点是找到一个算法n = m + 1 ≥ 4，因为一般情况下，我们可以使用类似于插入排序的算法来转换P，使得除了最后一个m + 1个元素匹配Q，具体情况(n, m) = (3, 2)可以通过检查解决。如果 m 是偶数，我们进一步确保转换与 Q 的奇偶性匹配，如有必要，通过旋转最后的 m 元素一次。 （对于 m 奇数，我们假设平价。）
我们需要一种技术来一次移动少于 m 个元素。假设状态如下
1, 2, 3, 4, ..., m, m + 1
旋转第二个 window m - 1 次（即反向一次）。
1, 3, 4, ..., m, m + 1, 2
旋转第 window 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 元素到位的 "insertion sort" 共轭。其他两个按奇偶校验顺序正确。