关于循环置换 [英] About Cyclic Permutation

问题描述

我是学数学的，我想出了这个问题。 有两个置换A和B以及一个整数M. 我们说几乎等于B，如果我们可以从让到B做以下操作。
-1选择的排列A.
一个M-长段 -2上执行它的循环移位向右。（因此，如果子段是1 2 3 4 5（M = 5），然后该操作后，这将是5 1 2 3 4。）

I studied math, and I come up with this problem. There are two permutations A and B and a integer M. We say A almost equal to B if we can make from A to B doing following operations.
-1 Choose a M-length segment of the permutation A.
-2 Perform a cyclic shift on it towards the right.(So,if sub segment is "1 2 3 4 5"(m=5), then after this operation , it will be "5 1 2 3 4".)

问：做了几乎等于B

我认为这是典型的，但我无法找到答案。 怎么解决呢？（不是蛮力！）

I think it is typical , but I couldn't find the answer. How to solve it?(not brute force!)

在排列＆LT元素个数= 10 ^ 5

number of elements in the permutation<=10^5

例如

一个1 2 3
B的2 3 1
米= 2
回答是
解释1 2 3 - >2 1 3 - >2 3 1

A "1 2 3"
B "2 3 1"
m=2
answer　YES
explain　"1 2 3"->"2 1 3"->"2 3 1"

推荐答案

这是我的猜想的证明。让 N 是排列的长度和 M 是，我们被允许旋转窗口，其中的长度 1≤M≤ñ。置换 P 和问：是直逼的，如果存在窗口旋转的转换序列 P 到问：。几乎平等是一种等价关系。下面是等价类的要求表征。

Here's a proof of my conjecture. Let n be the length of the permutations and m be the length of the windows that we are allowed to rotate, where 1 ≤ m ≤ n. Permutations P and Q are almost equal if there exists a sequence of window rotations that transforms P into Q. Almost equality is an equivalence relation. Here's the claimed characterization of the equivalence classes.

(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）的平价条件的必要性如下的事实，旋转奇数长度的窗口，是偶排列。

The first two claims are obvious. As for (3), the necessity of the parity condition follows from the fact that rotating a window of odd length is an even permutation.

在这里争论的肉是要找到一个算法时， N = M + 1≥4 ，因为在一般情况下，我们可以使用一种算法类似插入排序改造 P 让所有，但最后 M + 1 元素匹配问：，具体情况（N，M）=（3,2）可以通过检查解决。如果 M 甚至，我们还确保转换的奇偶性匹配问：，通过旋转，最后<$ C $ç> M 元素一次，如果有必要的。 （对于 M 奇怪，我们只是假设相等的奇偶性。）

The meat of the argument here is to find an algorithm for when n = m + 1 ≥ 4, since in general, we can use an algorithm similar to insertion sort to transform P so that all but the last m + 1 elements match Q, and specifically, the case (n, m) = (3, 2) can be solved by inspection. In case m is even, we ensure further that the transformation matches the parity of Q, by rotating the last m elements once if necessary. (For m odd, we just assume equal parities.)

我们需要的移动速度比 M 元素少一次的技术。假设状态如下。

We need a technique for moving fewer than m elements at once. Suppose that the state is as follows.

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

旋转第二个窗口 M - 1 倍（即在一次反向）

Rotate the second window m - 1 times (i.e., once in reverse).

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

我们已经成功地转动前三个元素。这足以与结合的组合通过旋转来插入排序第一米 - 1 元素的问：到位。另外两个是正确的顺序的奇偶校验一致。

We've succeeded in rotating the first three elements. This suffices in combination with conjugation by rotations to "insertion sort" the first m - 1 elements of Q into place. The other two are in the right order by the parity match.

这篇关于关于循环置换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！