我学的是数学,我想出了这个问题。
有两个排列 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"
最佳答案
这里证明了我的猜想。设 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
元素“插入排序”到位的结合结合。其他两个在奇偶匹配中顺序正确。
关于algorithm - 关于循环排列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32934075/