Array permutation through rotation and reverse operation

user_8994391 0
Viewed 227

Given a 1D array of length n. Is it possible to programmatically generate all possible permutations with just rotate and reverse operations applied as many times as required. If yes how(algo)? If not why? Here rotation can be by any d < n, and reverse means to reverse the entire array and not just in parts. Example: Array: 1,2,3,4 Reverse: 4,3,2,1 Rotate by 2: 3,4,1,2

Also given two permutation states A and B of an array. Is it possible to get from state A to state B programmatically using just rotation and reverse operations in any order. If yes how(algo)? If not why? Example: A: 5,3,1,2,4 B: 1,5,3,2,4

permutation reverse rotation arrays algorithm
1 Answers

No, you cannot.

Lets say you have any sequence of rotate and reverse operations. We'll write rotate by x as ROT(x) and reverse as REV.

Given any such sequence, you can transform it into an equivalent sequences consisting of at most one reverse followed by at most one rotation by applying the following rules:

rule 1: ROT(x), REV = REV, ROT(N-x)

For example, applying ROT(1), REV to 1234 gives 1234 -> 2341 -> 1432, and REV, ROT(3) gives 1234 -> 4321 -> 1432 -- the same result

By applying rule 1, we can move all the REV operations to the start.

rule 2: REV, REV = empty_sequence -- reversals cancel each other

Once all the REVs are at the start, we can apply rule 2 until there's at most one.

rule 3: ROT(x), ROT(y) = ROT(x+y % N) -- rotations add

also

ROT(0) = empty_sequence

Once all the ROTs are at the end, we can apply rule 3 until there's at most one.

So... any sequence of operations is equivalent to a sequence with at most one reverse followed by at most one non-zero rotation. There are only 2N such sequences, but there are N! permutations, so N!-2N permutations cannot be reached by any such sequence.

user_54835260
Related