在未排序和已排序列表之间找到最小距离

Question

假设 A 是一个列表，S 是一个相同元素按顺序排序的列表。假设所有元素都不相同。如何找到最小的一组“移动”（将 X 移动到 Y 的前面（或结尾）），使 A 变成 S？

举例：

A = [8,1,2,3]
S = [1,2,3,8]

A => S requires one move: 
   move 8 before end

A = [9,1,2,3,0]
S = [0,1,2,3,9]

A => S requires two moves:
   move 9 before 0
   move 0 before 1

我更喜欢JavaScript或Python，但任何编程语言都可以。

- georg

---

A = S怎么样？在我猜测的每种现代编程语言中都可以工作，其中未排序和已排序列表具有共同的基类。 - Martin Meeser

不确定这是否是最优解决方案，但问题可以简化为一个最短路径问题，其中source=A和target=S，使用包含所有排列的无权图，边是一种可能的移动。使用BFS算法的解决方案的复杂度将为O(n^d)，或者使用双向BFS的复杂度将为O(n^(d/2)) - 其中d是所需的最小“移动”次数。 - amit

你需要列出每个移动的名称，而不仅仅是它们的编号，对吗？我会尝试在接下来的几天内提供完整的解决方案和代码。 - Ivaylo Strandjev

请再看一下我的答案。我在里面添加了更详细的内容。 - Ivaylo Strandjev

这不就相当于找到最佳排序算法吗？ - martineau

Answer 1

这个问题等同于最长上升子序列问题。

你需要定义一个比较运算符less。less(a, b)将在目标序列中只有当a在b之前时返回true。现在，使用此比较运算符，计算源序列的最大递增子序列。您将需要移动每个不属于该子序列的元素(否则子序列将不是最大的)，并且您可以将其移动一次(将其移动到其目标位置)。

编辑:根据amit的要求，这里是我对上述陈述的证明: 我们将目标序列表示为B，将源序列表示为A。设n=|A|，设k为如上所述的最长递增序列的长度。

假设可以用比 n-k 更少的步骤从 A 到达B。 这意味着至少有 n-k+1 个元素不会移动。让 s₁,s₂,...s_m 成为不被移动的元素集合。 根据假设，我们知道 m > k。由于这些元素未移动，因此它们相对于彼此的位置不能改变。因此，所有这些元素在目标序列B中的相对位置与A中的位置相同。 因此，对于任何 i，j，定义中的 less(s_i, s_j) 运算符都应该成立。但是，如果这是真的，那么 s₁,s₂,...s_m 就构成了递增序列，而且因为 m > k，这就与 k 是最长递增序列的长度的假设矛盾。

现在，让我们展示一种算法，通过移动除了最长递增序列中的元素外的所有元素来从 A 到达 B。 我们将按照 B 中元素的顺序移动这些元素。 我们不会移动那些属于最长递增序列的元素。如果当前元素是B中的第一个元素，则将其简单地移到序列的开头。否则，我们将当前元素移动到前一个元素在B中的位置之后。请注意，这个元素可以是我们已经移动的前一个元素或者是最长递增序列中的元素。请注意，在我们即将移动索引为 i 的元素时，在索引 1,2,...i-1 处的所有元素都已经相对于彼此处于正确的位置。

编辑：添加一些代码以使答案更清晰。我不是JavaScript专家，所以请随意纠正或批评我的解决方案。

让我们定义一个函数transform(a, s)，它接受两个参数 - 如题所述的列表a和b。首先，我将创建一个映射positions，将a中的每个元素映射到其在s中的位置：

var positions = {};
for (var i = 0; i < a.length; ++i) {
  positions[a[i]] = i;
}

现在我有了这个数组，我可以定义一个辅助函数less，如我上面的答案所述。Less将使用两个值a和b（以及我刚创建的辅助映射），仅当a在s（目标列表）中排在b之前时返回true：

function less(a, b, positions) {
  return positions[a] < positions[b];
}

现在我不会描述如何找到相对于该比较运算符在a中找到最大递增子序列。你可以查看这个问题以获得详细的解释。我将简单地假设我已经定义了一个函数：

function max_increasing_subsequence(a, positions)

这将根据上述使用positions定义的比较运算符less，返回列表形式的a中最大递增子序列。我将使用您提供的第二个示例来说明我们目前的情况：

A = [9,1,2,3,0]
S = [0,1,2,3,9]

位置中的值将如下所示：

positions = { 0 : 0,
              1 : 1,
              2 : 2,
              3 : 3,
              9 : 4}

max_increasing_subsequence(a, positions)的结果将是[1, 2, 3]。顺便提一句，如果a中可能有重复元素，最好从max_increasing_subsequence返回索引而不是元素（在这个特定的示例中，差异将不可见）。

现在我将创建另一个辅助映射，以指示包含在最大递增子序列中的元素是哪些：

var included = {};
l = max_increasing_subsequence(a, positions);
for (var i = 0; i < l.length; ++i) {
  included[l[i]] = true;
}

现在，您可以通过对s进行单次迭代来完成解决方案。我将为最后一个元素添加一个特殊情况，以使代码更易于理解：

if (!(s[s.length - 1] in included)) {
  console.log("Move" + s[s.length - 1] + " at the end");
}
for (var i = s.length - 2; i >= 0; --i) {
  if (!(s[i] in included)) {
    console.log("Move" + s[i] + " before " + s[i + 1]);
  }
}

请注意，在上面的解决方案中，我假设每次记录新命令时，都是相对于数组a的顺序，在执行所有先前的命令后进行记录。

因此，总体而言，我认为transform应该是这样的：

function transform(a, s) {
  var positions = {};
  for (var i = 0; i < a.length; ++i) {
    positions[a[i]] = i;
  }
  var included = {};
  l = max_increasing_subsequence(a, positions);
  var included = {};
  for (var i = 0; i < l.length; ++i) {
    included[l[i]] = true;
  }
  if (!(s[s.length - 1] in included)) {
    console.log("Move" + s[s.length - 1] + " at the end");
  }
  for (var i = s.length - 2; i >= 0; --i) { // note s.length - 2 - don't process last element
    if (!(s[i] in included)) {
      console.log("Move" + s[i] + " before " + s[i + 1]);
    }
  }
}

我希望这段代码能让我的回答更清晰。

- Ivaylo Strandjev

---

你能证明这种方法的正确性吗？虽然我认为它是正确的，但我仍然想要确定它。 - amit

@amit 实际上，我大多数是通过实验来证明它的。我在各种计算机编程比赛中多次解决了完全相同的问题。这相当于众所周知的问题“如何用最少的步骤排序你所得到的卡牌”。 - Ivaylo Strandjev

其实，我认为正确性证明是相当简单的：考虑一个仅移动 k 个元素的有效解决方案。它不会改变其他 n-k 个元素的顺序，所以它们必须已经排序好了。然而，提出的算法找到的是最长的已排序子序列，因此它至少要保持 n-k 个元素不变。因此，它最多只会移动 k 个元素。 - Eyal Schneider

@amit，Eyal我已经添加了详细的证明，请查看。 - Ivaylo Strandjev

关于你的证明：难道你的意思不是“假设可以用比n-k更少的步骤从A到达B”吗？ - Eyal Schneider

Answer 2

如果您将两个列表视为两个字符串——例如，数字是ASCII编码的值——那么问题就等同于找到允许您将第一个字符串转换为第二个字符串的操作。转换次数是字符串之间的Levenshtein或编辑距离。

Levenshtein距离可以通过使用动态规划来找到，在矩阵中存储两个字符串所有前缀之间的距离，然后追溯您的步骤，以找到每行矩阵中哪个操作是最佳操作（需要最少的操作才能到达它）。

@IvayloStrandjev建议的最长递增子序列算法与最长公共子序列问题相关，而最长公共子序列问题又与编辑距离相关，作为仅允许插入和替换的替代度量标准。可能在空间上更有效，因为它利用了其中一个序列必须排序的事实；我只想提供一个我认为更容易理解的替代答案。

这里是Python中完整矩阵Levenshtein算法的实现，如上面链接的维基百科页面所述（最初在Wagner和Fischer的1974年论文中找到），也提供了正确性证明。我们还将操作名称存储在与操作分数相同大小的矩阵中，并在完成一行后打印最佳操作。

import argparse

import numpy as np


class Levenshtein(object):
    def __init__(self, string1, string2):
        self.string1 = string1
        self.string2 = string2
        self.scores_matrix = np.zeros(
            (len(self.string1) + 1, len(self.string2) + 1), dtype=np.int16)
        self.operations_matrix = np.empty_like(
            self.scores_matrix, dtype=(np.str_, 16))
        self.total_steps = 0

    def distance(self):
        m = len(self.string1) + 1
        n = len(self.string2) + 1
        for i in range(m):
            self.scores_matrix[i, 0] = i
        for j in range(n):
            self.scores_matrix[0, j] = j
        for j in range(1, n):
            for i in range(1, m):
                if self.string1[i - 1] == self.string2[j - 1]:
                    self.scores_matrix[i, j] = self.scores_matrix[i - 1, j - 1]
                    self.operations_matrix[i, j] = 'match'
                else:
                    self.scores_matrix[i, j] = self.select_operation(i, j)
                if j == n - 1:  # a row is complete
                    self.determine_best_op_and_print(i)
        return self.scores_matrix[m - 1, n - 1]

    def select_operation(self, i, j):
        possible_ops = ['delete', 'insert', 'substitute']
        ops_scores = [
            self.scores_matrix[i - 1, j] + 1,  # deletion
            self.scores_matrix[i, j - 1] + 1,  # insertion
            self.scores_matrix[i - 1, j - 1] + 1]  # substitution
        chosen_op = min(ops_scores)
        chosen_op_name = possible_ops[ops_scores.index(chosen_op)]
        self.operations_matrix[i, j] = chosen_op_name
        return chosen_op

    def determine_best_op_and_print(self, i):
        reversed_row = self.scores_matrix[i][::-1]
        reversed_pos_min = np.argmin(reversed_row)
        pos_min = len(self.scores_matrix[i]) - (reversed_pos_min + 1)
        best_op_name = self.operations_matrix[i, pos_min]
        if best_op_name != 'match':
            self.total_steps += 1
            print best_op_name, self.string1[i - 1], self.string2[pos_min - 1]


def parse_cli():
    parser = argparse.ArgumentParser()
    parser.add_argument('--list', nargs='*', required=True)
    return parser.parse_args()

if __name__ == '__main__':
    args = parse_cli()
    A = args.list
    S = sorted(A)
    lev = Levenshtein(A, S)
    dist = lev.distance()
    print "{} total steps were needed; edit distance is {}".format(
        lev.total_steps, dist)

以下是如何使用您提供的示例运行代码及预期输出：

$ python levenshtein.py --list 8 1 2 3
substitute 8 1
1 total steps were needed; edit distance is 2

$ python levenshtein.py --list 9 1 2 3 0
substitute 9 0
substitute 0 9
2 total steps were needed; edit distance is 2

- logc

Answer 3

这在很大程度上取决于问题的一些未说明的参数。首先，什么样的移动是合法的？只能相邻元素交换吗？还是任意删除和插入？其次，你只需要移动的次数还是需要一个具体移动列表？这会导致不同的算法：

1. 仅限相邻交换-如果您只关心最小数量，则称为逆序计数。 2. 删除、非相邻交换等-Levenshtein距离，前面提到的是更一般的编辑距离。一个技巧是如何定义移动集。将元素移动3个位置是否算一次移动，还是两次移动（删除和插入）？

逆序计数非常简单，可以使用一些基本的递归算法完成。您可以使用归并排序通过使用一个列表使另一个列表的转换版本来查找两个列表之间的逆序计数，其中新元素是索引。因此，如果有两个序列，您可以执行以下操作：

sequence = [seq2.index(element) for element in seq]

一个简单的纯Python归并排序实现来计算逆序对的方法如下：

if len(sequence) <= 1:
    return 0, sequence
else:
    firstHalf = sequence[:int(len(sequence)/2)]
    secondHalf = sequence[int(len(sequence)/2):]
    count1, firstHalf = mergeSortInversionCount(firstHalf)
    count2, secondHalf = mergeSortInversionCount(secondHalf)
    firstN = len(firstHalf)
    secondN = len(secondHalf)
    secondHalfEnd = secondN
    count3 = count1 + count2
    # Count the inversions in the merge
    # Uses a countdown through each sublist
    for i in xrange(firstN-1, -1, -1):
        x = firstHalf[i]
        inversionFound = False
        for j in xrange(secondHalfEnd-1,-1,-1):
            if x > secondHalf[j]:
                inversionFound = True
                break
        if inversionFound:
            secondHalfEnd = j+1
            count3 += j+1
    mergeList = firstHalf + secondHalf
    mergeList.sort()
    return count3, mergeList

这只是将列表分成两半并计算逆序对的数量，同时排序列表。就算法而言，归并排序相当有效率（NlogN），但从实际角度来看，你可以通过一些numpy矩阵或通过对底层Python排序算法的C代码进行轻微改进来更快地计算它。技术上讲，由于该方法将任何类型的变量转换为数字，因此基本上只缩减为列表排序方法，所以您可以使用其他逐元素列表排序来完成相同的操作，只要跟踪计数即可。

使用任何这些方法（逆序对计数、Levenstein等），您都可以记录移动。逆序对计数记录交换次数，logc指出了用于记录Levenstein某些更一般移动的合理方法。个人而言，我倾向于使用逆序对计数，因为它们相当简单。但这非常取决于您想要什么。如果您需要比两个相邻元素交换更多的操作，则Levenstein是一个明显的选择。

- Namey

Answer 4

执行循环排序并计算移动次数。这保证是最小数量。

- AShelly