查找未排序和排序列表之间的最小距离

Question

设A为列表,S为相同元素的排序列表.假设所有元素都不同.如何找到move X before Y (or end)将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,但任何语言都可以.

Answer 1

这个问题相当于增长最长的子序列问题.

您必须定义比较运算符less.当且仅当在目标序列之前时less(a, b)才会返回.现在使用此比较运算符,计算源序列的最大增加子序列.您将必须移动不属于此子序列的每个元素(否则子序列将不是最大值),您可以将其移动一次(将其移动到其目标位置).trueab

编辑:根据amit的要求,这是我对上述陈述的证明:让我们表示目标序列,B并让我们表示源序列A.设n = |A|并且k设为如上所述的最长增加序列的长度.

• 让我们假设它是有可能达到B的A比少运动n - k.这意味着至少n - k + 1来自的元素A不会被移动.设s ₁,s ₂,... s _m是未移动的元素集.从我们的假设我们知道m > k.现在由于这些元素没有移动,它们相对于彼此的相对位置不能改变.因此,目标序列中所有这些元素的相对位置与B中的相同A.为此操作者更少(一个或多个_我,S _Ĵ如上所定义)应该是任何真i,j.但如果这是真的那么s ₁,s ₂,... s _m是递增序列,并且因为m > k这导致与假设k是最长增加序列的长度的矛盾.
• 现在让我们展示一个算法,通过移动所有元素来达到B,A但这些元素是最长增长序列的一部分.我们将按照它们在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将采用两个值a和b(以及我刚创建的辅助映射)并且当且仅当在(目标列表)a之前时返回true :bs

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

现在我不会描述我们如何找到a与该比较运算符相关的最大增加子序列.您可以查看此问题,以获取有关如何执行此操作的详细说明.我将简单地假设我定义了一个函数:

function max_increasing_subsequence(a, positions)

这将返回a相对于less如上定义的比较运算符(使用positions)作为列表的最大增加子序列.我将用你的第二个例子来说明我们到目前为止所做的事情:

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在执行完所有先前命令后立即记录数组的顺序.

总的来说,我认为转换看起来应该是这样的:

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]);
    }
  }
}

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

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