Optimal algorithm to reorder two arrays putting the common elements first

Let's say we have two arrays having some elements in common (the arrays can't contain duplicates)

Array 1 = [A, K, C, F]
Array 2 = [B, D, C, K]

I would like to reorder the two arrays with the following requirements:

  • The common elements must be at the beginning of the arrays (without any specific order)
  • The common elements in the two arrays must be exactly at the same positions
  • The non-common elements can be in any position (after the common ones)
  • Swapping two elements which are farther away costs more than swapping two elements which are closed together (we can assume a linear cost function where cost of swapping elements at indexes i and j = abs(i - j))

For the example above having [C, K] in common, we could produce the following valid rearrangement:

Array 1 = [C, K, A, F]
Array 2 = [C, K, B, D]

Another valid rearrangement could be:

Array 1 = [K, C, A, F]
Array 2 = [K, C, B, D]

Although it is quite trivial to write a basic algorithm that swaps the two input arrays to generate a valid output, it is not clear to me how to write the "optimal" (in sense of minimal costs) one.

I am not even sure if this algorithm could be solved using dynamic programming or similar techniques. Has anyone already seen this problem somewhere before or has an idea on how to solve it?

1 answer

  • answered 2018-11-07 23:29 Jan Weimer

    I will describe my ideas, sorry for my english:

    First, find out which are the common elements.

    Second, go through both list, at the same time, from the left to the right. There might be three cases:

    a) there are no common elements in the position. You go to the next position.

    b) there is one common element in the position. Then you swap the common element and its complement to the most left position not occupied by common elements.

    c) there are two common elements in the position. Then you swap the one to the most left position not occupied by common elements or the next position to the right and add the complements. If this position is also occupied by one or two common elements, you keep these in a store and try to empty this store while moving on. Realize that this store can grow larger than one or two elements.

    By this you should be able to extract where to move which element, with an optimal solution with respect to your requirements.

    remark: This seems quite logic to me now but it would be nice to know how it worked ;)