3
$\begingroup$

Say I have an array that goes like [ a, c, b, d ] and I want it rearranged as [ d, c, a, b ]. The only type of change I'm allowed to make is plucking an element from one place and inserting it into another. Also, the array stays continuous with no empty indices, for example if I pluck c from [ a, c, b, d ] it becomes [ a, b, d ] until I reinsert c.

Is there an algorithm to figure out a minimal sequence of such changes in order to complete the transformation?

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
2
$\begingroup$

If you look at the set of elements you do not move, this set must form a common subsequence of the input string and the target string. Therefore, the number of elements you do not move cannot be longer than a longest common subsequence. On the other hand, all the other elements can be moved to their correct places in one move. Therefore the algorithm goes like this:

  • find a longest common subsequence
  • move all the other elements

Finding a longest common subsequence can be done in quadratic time.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.