2
$\begingroup$

Say I have an array of numbers, e.g. [0, 1, 2, 3, 4, 5] and I want to end up with an array, e.g. [2, 1, 4, 0, 5, 3]. At my disposal, I have a single method that I can use:

move(fromIndex, toIndex)

Thus, to achieve my desired array, I could call the method a number of times:

move(2, 0); // [2, 0, 1, 3, 4, 5]
move(1, 2); // [2, 1, 0, 3, 4, 5] (swapped 2 with 0)

move(4, 2); // [2, 1, 4, 0, 3, 5]
move(3, 4); // [2, 1, 4, 3, 0, 5] (swapped 4 with 0)

move(4, 3); // [2, 1, 4, 0, 3, 5] (swapped 0 with 3)

move(5, 4); // [2, 1, 4, 0, 5, 3] (swapped 5 with 3)

Thus, I also have a list of move() operations to achieve my desired result. The list of move() operations can possibly be reduced in size by changing the order and the indexes, to end up with the same result.

Is there an algorithm that I can use on my list of move() operations to reduce its size to a minimum?

$\endgroup$
  • 2
    $\begingroup$ This post can answer your question. Though that post requires the target array to be sorted, it is essentially the same problem as yours. $\endgroup$ – xskxzr Apr 19 at 10:14
  • $\begingroup$ @xskxzr it works perfectly indeed, the point is just to start from the unsorted sequence. I was thinking on how to extract the longest sorted sub-sequence, and it is quite a tough work in fact requiring DP. $\endgroup$ – Vince Apr 19 at 13:42
  • $\begingroup$ Can you just do quicksort on the unsorted array? For every sequence of moves in quicksort: $\{\text{move}(i_1, j_1), \text{move}(i_2, j_2), \ldots \text{move}(i_n, j_n)\}$. We just reverse those in the original sorted array to get the final one: $\{\text{move}(j_n, i_n), \text{move}(j_{n-1}, i_{n-1}), \ldots \text{move}(j_1, i_1)\}$. This might not be minimum, but will give a decent asymptotic upper bound depending on the sorting method you use. $\endgroup$ – ryan Apr 19 at 16:29
  • 1
    $\begingroup$ Is the question essentially "Algorithm to find minimum number of move/swap operations to convert list1 to list2"? $\endgroup$ – AzureMinotaur Apr 20 at 1:24
  • $\begingroup$ @AzureMinotaur It seems an interesting question to devise an efficient algorithm that computes the minimum number of operations to convert list1 to list2, where each operation is either a move or a swap. Here is an example where both kinds of operation are useful, (2,3,1,6,5,4) and (1,2,3,4,5,6). $\endgroup$ – Apass.Jack Apr 23 at 10:56
0
$\begingroup$

The example in the question

The minimum number of moves needed for the example in the question, from [0, 1, 2, 3, 4, 5] to [2, 1, 4, 0, 5, 3] is 3.

            // [0, 1, 2, 3, 4, 5], where 2, 4, 5 are good.
move(2, 1); // [0, 2, 1, 3, 4, 5], where 2, 1, 4, 5 are good.
move(0, 4); // [2, 1, 3, 4, 0, 5], where 2, 1, 4, 0, 5 are good.
move(2, 5); // [2, 1, 4, 0, 5, 3], where 2, 1, 4, 0, 5, 3 are good.

The idea is to split the target array into two subsequences, 2, 4, 5 and 1, 0, 3 where the first subsequence is the longest increasing subsequence. Keeping the order of elements in the first subsequence, we will move the remaining elements from left to right to their expected positions respectively, i.e, first moving 1 to its expected positions and so on.

An algorithm

Input: Array $A = [0, 1, 2, ..., n-1]$ and array $B[0], B[1], ..., B[n-1]$ which is a permutation of $0, 1, 2, ..., n-1$.

Output: A list of minimum size each of whose elements is an operation of the form move(fromIndex, toIndex) such that after performing that list of operations on $A$, $A$ becomes $B$.

Procedure: $B$ is intact while $A$ will be changed move by move.

  1. Let $B[s_1], B[s_2], \cdots, B[s_m]$ be the longest increasing subsequence of $B$. This can be done as described in this Wikipedia article. It can also be done as described in this Wikipedia article since the longest increasing subsequence of $B$ is the longest common subsequence of $A$ and $B$. Let $s_{-1}=-1$ and $s_{m+1}=n$.
  2. Let $O$ be an empty list of operations. For $i$ from -1 to $m$ inclusive do:

    • For $j$ from $1$ inclusive to $s_{i+1} - s_i $ exclusive do:

      1. Find $x$, the index of $B[s_i]$ in $A$. If $i=-1$, let $x=0$.
      2. find $y$, the index of $B[s_j + j]$ in $A$.
      3. Move $A[y]$ to the $j$-th place after the place of $A[x]$.
      4. Add $\text{move}(y, x + j)$ to $O$.

      Now all numbers in $B$ up to index $s_{i+1}$ are good, i.e., sorted in the same order in $A$ and in $B$, although the same number might be at different indices in $A$ and in $B$.

Correctness

It is clear that at the end of the algorithm, all numbers in $A$ are sorted in the same order in $B$ and in $B$, i.e., $A$ is $B$. The total number of moves in the algorithm is $$(s_0-s_{-1}-1) + (s_1-s_{0}-1)+\cdots + (s_{m+1}-s_{m}-1) = s_{m+1}-s_0-(m+1)=n.$$

On the other hands, each move(fromIndex, toIndex) in any algorithm can increase the common longest subsequence between $A$ and $B$ by at most 1. So $n-m$ moves are needed.

This is pointed out by xskxzr first.

Complexity

It takes $O(n\log n)$ or $O(n^2)$ to find the longest increasing subsequence. Finding the index of a number in $A$ is performed about $2n$ times, which costs $O(n^2)$ in total. It takes $O(n^2)$ to perform all $n$ moves. So the algorithm runs in $O(n^2)$ time.

The implementation of finding the index of a number can be sped up so that the algorithm can be implemented to run in $O(n\log n)$ time.

Exercises

Exercise 1. (One minute or two) Array $A$ is a permutation of $0, 1, \cdots, n-1$. State an algorithm that find a list of operations of the form move(fromIndex, toIndex) such that will sort $A$ in minimum steps.

Exercise 2. The same input is given. Find an algorithm that computes the minimum number of moves needed to change $A$ so that it ends up the same as $B$ up to a cyclic shift. For example, when $B=[2, 1, 4, 5, 0, 3]$, $A$ should be changed to one of $[2, 1, 4, 5, 0, 3]$, $[1, 4, 5, 0, 3, 2]$, $[4, 5, 0, 3, 2, 1]$, $[5, 0, 3, 2, 1, 4]$, $[0, 3, 2, 1, 4, 5]$ and $[3, 2, 1, 4, 5, 0].$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.