3
$\begingroup$

I have 2 arrays, A and B, which each contain the same N elements, but in a different order. (A different permutation) There are also no duplicates in A and B.

I'm trying to devise an algorithm which generates a series of moves, which changes A into B.

A move means to move one element in an array to another position (not a swap though). An example of a move would be:

1
2
3

Move index 2 to index 0 would be:

3
1
2

Now it should always be possible to change A to B in less than N moves. However, the hard part for me is that one requirement is that the series of moves which are generated should be able to be applied sequentially, so something like this should work:

let A = .....
let B = .....

let moves = generate_moves(A, B)

foreach move in moves:
    A.move(move.from, move.to) // Moves the element at move.from to move.to

Assert(A == B)

The key is that the resulting moves should be able to be applied sequentially, and each time a move occurs, the indices in the entire array shift, so therefore the next moves need to take into account the shifting indices.

Example:

Suppose array A is as follows:

5
1
3
2
4

And B is as follows:

1
4
3
5
2

Then one set of moves that could be produced to get from A to B is:

Move index 1 to 0
Move index 4 to 1
Move index 3 to 2

What I tried:

I made an algorithm like this:

  1. Go through each element in B
  2. If the element at the same position in A is wrong, then output a move that moves the correct element into position
  3. Repeat until B is exhausted

This works, except you need to keep bookmarking information for A, because every move changes the indices of the elements above the move source.

So I used a tree structure to store the bookmarking information.

Therefore, the above mentioned algorithm takes O(n log n) time, because I need to shift my source indices for the move by an offset which is stored in the tree.

My question is: Is it possible to make an algorithm to do this task in O(N) time, but without ever generating more than N moves?

It seems this problem has some similarities to this problem, because it also involves recovering the indices of elements after they have been offset at any point in time.

$\endgroup$
5
  • $\begingroup$ Are the elements of both arrays the permutation of the integers in $[1,...,n]$. If not and elements are arbitrary but can be compared to each other, then how do you determine the correct positions of each elements of $A$ with respect to $B$ in $O(n)$ time. Since this seems to be related to the inversion in $A$ with respect to $B$, which requires at least $\Omega(n \log n)$ $\endgroup$
    – Russel
    Commented Dec 18, 2022 at 23:40
  • $\begingroup$ @Russel No, the elements are arbitrary. I determine where the positions of the elements are in amortized O(1) time by storing them in a Hash table and an array, similar to a HashSet but with an ordering for the elements. $\endgroup$ Commented Dec 19, 2022 at 0:17
  • $\begingroup$ @Russel But the problem I'm encountering is that when I determine where the correct position for the elements in A should be, I need to output a "Move" to move that element into the correct position. But, when I do that move, the indices of the elements above that move get offsetted by 1. So I need to store those offsets, and I can retrieve them in at best O(log n) time. For each element, this is about O(n log n) time. $\endgroup$ Commented Dec 19, 2022 at 0:21
  • $\begingroup$ I assume that if H is the hash table representing the indices of $B$, e.g. H["1"] will give you the position of element "1" in $B$. In your example, your first move is to move element "2" from 1 to 0, after that do skip moving element "1"? $\endgroup$
    – Russel
    Commented Dec 19, 2022 at 0:50
  • $\begingroup$ @Russel Oh no, sorry, I should've clarified! The first example with the "123" thing was just to show what a move was defined as. I'll list a real example! $\endgroup$ Commented Dec 19, 2022 at 1:03

2 Answers 2

1
$\begingroup$

As I have mentioned in my comment, your problem is indeed related to the counting the number of inversions, which can be shown to have a lower-bound of $\Omega(n \log n)$ if you are to only allowed to compare elements.

To see this, let $x$ and $y$ be some elements, such that $x$ comes before $y$ in $B$. In your solution, you traverse $B$ in order and create a move to transfer an item in $A$ to its correct position in $B$. Therefore, $x$ will be moved first before $y$. Now, the position of $y$ in $A$ will only be affected if $y$ comes before $x$ in $A$, or if $x$ and $y$ is an inversion in $B$. So if you are to find the final position of $y$ in $A$ when you are to create the move to transfer $y$ in its correct position, you have to determine how many inversions are there in $B$ with respect to $y$ to determine the amount of offset to add to $y$'s original position in $A$. This you have to do with all $n$ items.

So your current solution that requires additional $O(n \log n)$ time to track the position of elements is necessary. But I think you can make it simpler if you would compute the number of inversions upfront, before creating the moves, using an $O(n \log n)$ solution rather than maintaining a tree structure that you need to update each time a move is created.

$\endgroup$
1
$\begingroup$
  • Build a map between each value and its index for list B.
  • Repeat until finished.
    • Find index of value of first element of list A.
    • Swap position 1 and the indexed position within list A.
    • If A[1] = B[1], work with 2 instead of 1 (etc. for 3, 4, …).
$\endgroup$
2
  • 1
    $\begingroup$ Thank you for the answer! However, this solution uses swaps, but those are different than moves. (A "move" moves an element, shifting the rest down, whereas a swap just swaps the elements). (I will clarify this in the post) $\endgroup$ Commented Dec 19, 2022 at 2:26
  • 1
    $\begingroup$ A swap can be replicated using 2 moves, but the issue is there can be up to N possible swaps, therefore 2N possible moves using this algorithm. However, A can always be "moved" to B in N moves. $\endgroup$ Commented Dec 19, 2022 at 2:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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