Ordering a number array by shifting

[Detektyw]

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² T1(n-1) shifts and ~0.5n² T2(2) shifts. This way we get O(n) for checking whether the solution is sorted, times O(2ⁿ³), hence O(n2ⁿ³)).

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

 

[KataKoniK]

your first step would be to analyze the problem and see if there are any patterns or properties that can be exploited to find a more efficient solution.

One possible approach could be to think about the final sorted array and work backwards to see what operations would need to be performed to get to that state. For example, if we consider the example given in the problem statement where n=4 and the initial array is [3,2,1,4], the final sorted array would be [1,2,3,4]. Working backwards, we can see that the first operation would need to be a T2(2) to move the 3 to the front, followed by a T1(1) to shift the 2 to the back. This gives us [2,3,4,1]. Next, we would need a T2(1) to move the 2 to the front and a T1(1) to shift the 3 to the back, giving us [3,4,1,2]. Finally, we would need a T1(2) to shift the 3 and 4 to the back, giving us the final sorted array [1,2,3,4]. This sequence of operations has a length of 5, which is much smaller than n^2 for n=4.

From this example, we can see that the key is to find a way to efficiently move the elements to their correct positions. This can be done by first finding the position of each element in the final sorted array and then determining the minimum number of operations needed to move that element to its correct position.

Another approach could be to use a sorting algorithm such as bubble sort or insertion sort, which can be implemented in O(n^2) time. These algorithms use a combination of swaps and shifts to sort the array, which are similar to the operations given in the problem statement.

In conclusion, as a scientist, your task would be to analyze the problem, identify patterns and properties, and come up with an efficient algorithm to solve it. You may also want to consider different approaches and compare their efficiency to find the most optimal solution.