- #1

Detektyw

- 6

- 0

## Homework Statement

Given a permutation of the set {1,...,n} for a natural n, and two possible operations on this set:

Type-1(k): Shift the first element in the array to the back of it, do it k times.

[3,2,1,4] -> T1(1) -> [2,1,4,3]

Type-2(k): Shift the third element in the array to the front, do it k times.

[3,2,1,4] -> T2(1) -> [1,3,2,4]

Determine whether it is possible to sort it in an increasing order, and if so, find the sequence of operations necessary to do this. The length of the sequence of operations has to be equal to or smaller than n^2.

## Homework Equations

- None so far.

## The Attempt at a Solution

So far, I've gotten an algorithm which is correct, however way too slow.

It is based on the following observations:

* T1 is periodic in n, since V -> T1(|V|) -> V,

* T2 is periodic in 3, since V -> T2(3) -> V

Now, starting with the initial positions, we can test the effects of a T1 move and T2 move, check whether they yield a sorted array, if not, for each of them do the same.

Recursion then bottoms out when

a) the length of the move sequence exceeds n^2

b) it would be forced to make third T2 move in a row

c) or n-th T1 move in a row

If the main recursion returns without having found a solution, this means there is none which fit the description.

This one clearly works, but it does so in an abysmal complexity (worst case, don't know if it can happen, would be a solution n^2 long, consisting of ~0.5n

^{2}T1(n-1) shifts and ~0.5n

^{2}T2(2) shifts. This way we get O(n) for checking whether the solution is sorted, times O(2

^{n3}), hence O(n2

^{n3})).

Any help with finding a more optimal solution (polynomial time) would be appreciated.

Last edited: