arrays - 通过旋转和反向操作进行数组置换

Question

给定一个长度为 n 的一维数组。是否有可能以编程方式生成所有可能的排列，只需根据需要多次应用旋转和反向操作。如果是，如何(算法)？如果不是为什么？ 这里的旋转可以是任何 d < n，而 reverse 意味着反转整个数组，而不仅仅是部分。 例子: 数组:1,2,3,4 反向:4,3,2,1 以 2 为单位旋转:3,4,1,2

还给出了数组的两个排列状态 A 和 B。是否可以仅使用任何顺序的旋转和反向操作以编程方式从状态 A 进入状态 B。如果是，如何(算法)？如果不是为什么？ 例子: 答:5,3,1,2,4 B: 1,5,3,2,4

Answer 1

不，你不能。

假设您有任意顺序的旋转和反向操作。我们将按 x 旋转写为 ROT(x)，将反向写为 REV。

给定任何这样的序列，您可以通过应用以下规则将其转换为一个等价序列，该等价序列包含最多一个反转和最多一个旋转:

规则 1:ROT(x)，REV = REV，ROT(N-x)

例如，将ROT(1)、REV应用于1234会得到1234 -> 2341 -> 1432，而REV , ROT(3) 给出 1234 -> 4321 -> 1432 -- 结果相同

通过应用规则 1，我们可以将所有的 REV 操作移到开头。

规则 2:REV，REV = empty_sequence -- 反转相互抵消

一旦所有的 REV 都在开头，我们就可以应用规则 2，直到最多有一个。

规则 3:ROT(x), ROT(y) = ROT(x+y % N) -- 旋转相加

还有

ROT(0) = empty_sequence

一旦所有的 ROT 都结束了，我们就可以应用规则 3，直到最多有一个。

所以...任何操作序列都等价于最多有一个反向后跟最多一个非零旋转的序列。 只有2N个这样的序列，但是有N!个排列，所以N!-2N个排列不可能由任何这样的序列到达。