How to reduce number of move operations in an array?
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)
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?
sorting arrays ordering
HelloWorldHelloWorld
$\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 '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$ – Optidad Apr 19 '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 '19 at 16:29
$\begingroup$ Is the question essentially "Algorithm to find minimum number of move/swap operations to convert list1 to list2"? $\endgroup$ – AzureMinotaur Apr 20 '19 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$ – John L. Apr 23 '19 at 10:56
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.
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$.
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:
Find $x$, the index of $B[s_i]$ in $A$. If $i=-1$, let $x=0$.
find $y$, the index of $B[s_j + j]$ in $A$.
Move $A[y]$ to the $j$-th place after the place of $A[x]$.
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$.
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.
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.
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].$
John L.John L.
Not the answer you're looking for? Browse other questions tagged sorting arrays ordering or ask your own question.
What is the min # of moves to sort an array from 1 to n?
Counting number of sums from contiguous subarrays of an array
Sorting array with at most two inversions
How can I use prefix sum of an array to solve this problem?
What is total work of managing the dynamic array and why is it the same as for fixed array - O(n)
Is my algorithm a $O(nm \lg m)$ solution for sorting a row and columnwise sorted $2D$ array?
Transforming an array into one with descending order
Minimum number of adjacent swaps needed to sort a circle of elements