1

我正在尝试解决一个难题，但恐怕我遇到了障碍——我不知道如何解决它。我想也许这里有人偶然发现了类似的东西，如果没有，我相信那些喜欢制作算法的人会喜欢尝试找到解决方案：

我们得到一个未排序的数组。我们可以进行以下两种移动之一：从数组中取出任何元素并将其移动到数组的开头或结尾。我们还得到了数组最终应该是什么样子。我们应该用最少的步数对数组进行排序。

例子：

 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

已达到目标数组，最小步数为 3。

有谁知道如何解决这个问题？

4

5 回答 5

4

我相信诀窍是找到两个数组之间的最长公共子序列（您可以在 O(n^2) 时间内找到它。这将为您提供最大可能的不必移动的数字集，反之，必须移动的最小可能数字集。一旦你有了必须移动的数字集，弄清楚如何移动它们应该是相当简单的。

在您的示例中：

(5, 1, 4, 3, 2) 和 (3, 1, 2, 5, 4) 之间的最长公共子序列是 (1, 4), (1, 2), (3, 2) 或 (5 , 4). 每个子序列都告诉您最小移动数是 3（尽管您选择的移动对于每个子序列都会不同，显然）。

编辑

我认为这基本上是正确的答案（沃恩有一些变化）。

首先，我们像往常一样为最长公共子序列问题构建我们的子序列长度数组（M[i][j] = 以 source[i] 和 target[j] 结尾的最长公共子序列的长度）。

然后，我们不是选择解决方案，而是枚举所有可能的最长公共子序列。

然后我们为每个子序列分配一个分数，这是目标序列中最长的连续块的长度。

在示例中，我们得到：

(1, 2) - 得分 2 (1, 4) - 得分 1 (3, 2) - 得分 1 (5, 4) - 得分 2

我们选择任何得分最高的序列，并生成适当的移动指令以在该序列之前或之后移动剩余的数字。

于 2013-01-10T14:42:24.717 回答
0

您可以使用 A* / IDA* 搜索算法来做到这一点。您已经有了“开始”和“目标”，启发式函数可以是有序子数组的数量。新节点的创建是元素到开始/结束的过渡......让算法发挥作用

于 2013-01-10T18:54:49.773 回答
0

如果您遵循@High Performance Mark 的建议，您可以取消排名机制。对于您的阵列，重新标记将是 (4, 2, 5, 1, 3)。在此，LCS 是 (4, 5) 和 (2,3)。因此，您可以直接从其中任何一个开始并移动中间的那些：

对于 4,5：按降序查看小于 4 的并将它们移到前面。然后对于大于 5 的按升序排列

  • 4, 2, 5, 1, 3 (开始) --> 3
  • 3, 4, 2, 5, 1 --> 2
  • 2, 3, 4, 5, 1 --> 1
  • 1、2、3、4、5（完）

对于 2,3：按降序查看小于 2 的并将它们移到前面。然后对于大于 3 的按升序排列

  • 4, 2, 5, 1, 3 (开始) --> 1
  • 1, 4, 2, 5, 3 --> 4
  • 1, 2, 5, 3, 4 --> 5
  • 1, 2, 3. 4, 5 (完)

每个都有三个动作。

于 2013-01-10T22:50:44.687 回答
0

如果 O(n^2) 解决方案足够好，则有一个非常简单的算法。

进行 n 次迭代，其中 n 是数组的长度。在迭代 i 中，在元素 i 到 n 中找到在目标排列中具有最高位置的元素，并将其移动到数组的开头。

迭代 1 将应该最后的元素移动到开始。迭代 2 将应该在倒数第二个的元素移动到紧接在它之前的元素。...迭代 n 将最后一个元素（应该是第一个元素）移动到数组的开头。

于 2013-01-10T15:03:14.857 回答
0

我确实同意 ArunMK，但他的描述相当缺乏。因此，我建议在 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();
      }
    }
  }
}

输出是：

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
于 2013-01-13T22:57:28.747 回答