Sort an array by moving elements only to the beginning or the end

Question

I am trying to solve a difficult problem, and I'm afraid I've hit a roadblock - I'm out of ideas how to solve it. I thought maybe someone on here has stumbled upon something similar and, if not, I'm sure that those that like making algorithms will enjoy trying to find a solution:

We are given an unsorted array. We are allowed to make one of two moves: take any element out of the array and move it either to the beginning or the end of the array. We are also given what the array should look like in the end. We are supposed to sort the array with the minimum number of steps.

Example:

 5 1 4 3 2 - > starting array
 3 1 2 5 4 - > target array

 Steps: move 5 to the end 1 4 3 2 5 
 move 3 to the beginning  3 1 4 2 5
 move 4 to the end  3 1 2 5 4

The target array has been reached, the minimal number of steps is 3.

Does anyone have any idea on how to solve this?

Answer 1

I believe the trick is to find the longest common subsequence between the two arrays (you can find this in O(n^2) time. This will give you the largest possible set of numbers that don't have to move, and conversely, the smallest possible set of numbers that do have to move. Once you have the set of numbers that must move, it should be fairly trivial to figure out how to move them.

In your example:

The longest common subsequence between (5, 1, 4, 3, 2) and (3, 1, 2, 5, 4) is (1, 4), (1, 2), (3, 2), or (5, 4). Each subsequence tells you that the minimum number of moves is 3 (though the moves you pick will be different for each, obvisously).

EDIT

I think this is basically the right answer (with some changes from Vaughn).

First, we build our array of subsequence lengths as usual for the longest common subsequence problem (M[i][j] = length of the longest common subsequence ending at source[i] and target[j]).

Then, instead of picking a solution, we enumerate all possible longest common subsequences.

We then assign a score to each subsequence which is the length of the longest contiguous block in the target sequence.

In the example, we get:

(1, 2) - score 2 (1, 4) - score 1 (3, 2) - score 1 (5, 4) - score 2

We pick any sequence with the maximum score and generate the appropriate move instructions to move the remaining numbers before or after this sequence.

Answer 2

If an O(n^2) solution is good enough there is a really simple algorithm.

Do n iterations, where n is the length of the array. On iteration i, find the element, among elements i through n, that has the highest position in the target arrangement, and move it to the start of the array.

Iteration 1 moves the element that should be last to the start. Iteration 2 moves the element that should be next to last to immediately before it. ... Iteration n moves the final element, the one that should be first, to the start of the array.

Answer 3

You can do that with A* / IDA* search algorithm. you already have the "Start" & "Goal" a heuristic function can be number of ordered sub arrays. the creation of new nodes cais the transition fo elements to the start/end ...and just let the algorithm do the magic

Answer 4

You can do away with the ranking mechanism if you follow @High Performance Mark's advice. For your array the relabelling will be (4, 2, 5, 1, 3). In this, the LCS are (4, 5) and (2,3). So you can start from any of these directly and move the ones in the middle:

For 4,5: look at ones smaller than 4 in descending order and move them front. Then for ones larger than 5 in ascending order

• 4, 2, 5, 1, 3 (start) --> 3
• 3, 4, 2, 5, 1 --> 2
• 2, 3, 4, 5, 1 --> 1
• 1, 2, 3, 4, 5 (end)

For 2,3: look at ones smaller than 2 in descending order and move them front. Then for ones larger than 3 in ascending order

• 4, 2, 5, 1, 3 (start) --> 1
• 1, 4, 2, 5, 3 --> 4
• 1, 2, 5, 3, 4 --> 5
• 1, 2, 3. 4, 5 (end)

Each has three moves.

Answer 5

I do agree with ArunMK but his description is quite lacking. Thus I propose an implementation in C.

#include <stdio.h>
int start[] = { 5, 1, 4, 3, 2 };
int target[] = { 3, 1, 2, 5, 4 };
const int length = sizeof(start) / sizeof(*start);
int canon[length];

void dump_canon()
{
  int i;
  for (i = 0; i < length; i++)
    printf("%d ", target[canon[i]]);
  printf("\n");
}

int main()
{
  int i, j, k;

  /* First "relabel" the array so that the problems becomes: sort the array. */
  for (i = 0; i < length; i++) {
    for (k = 0; start[i] != target[k]; k++)
      /* NO-OP */;
    canon[i] = k;
  }
  printf("Start ");
  dump_canon();
  /* Search for the longuest ascending sequence without holes */
  int longuest_start;
  int longuest_length = 0;
  for (i = 0; i < length; i++) { /* Use i + longuest_length < length for optimisation */
    k = 1;
    for (j = i + 1; j < length; j++) { /* condition can be optimized */
      if (canon[i] + k == canon[j])
        k++;
    }
    if (k >= longuest_length) {
      longuest_start = canon[i];
      longuest_length = k;
    }
  }

  /* Now longuest_start has longuest_length ordered values */
  /* Increase this ordered values stride by picking a number to put just before or after it */
  while (longuest_length < length) {
    for (i = 0; i < length; i++) {
      if (canon[i] + 1 == longuest_start) {
        k = canon[i];
        for (j = i; j > 0; j--)
          canon[j] = canon[j - 1];
        canon[0] = k;
        longuest_start--;
        longuest_length++;
        printf("Take %d and move it to the beginning: ", target[k]);
        dump_canon();
      }     
      else if (canon[i] == longuest_start + longuest_length) {
        k = canon[i];
        for (j = i; j < length - 1; j++)
          canon[j] = canon[j + 1];
        canon[length - 1] = k;
        longuest_length++;
        /* XXX We just shifted a new value here, redo this index */
        i--;
        printf("Take %d and move it to the end: ", target[k]);
        dump_canon();
      }
    }
  }
}

Output is:

Start 5 1 4 3 2 
Take 5 and move it to the end: 1 4 3 2 5 
Take 4 and move it to the end: 1 3 2 5 4 
Take 3 and move it to the beginning: 3 1 2 5 4