查找未排序列表和排序列表之间的最小距离
设A是列表，S是相同元素的排序列表。假设所有元素都不同。如何找到将A转换为S的最小“移动”集(move X before Y (or end))？
示例：
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，但是任何语言都可以。
回答 3
Stack Overflow用户
发布于 2014-02-16 14:07:55
如果您将两个列表看作两个字符串--例如，数字是ASCII编码中的值--那么问题就相当于找到允许将第一个字符串转换为第二个字符串的操作。操作的数量依次是字符串之间的Levenshtein或编辑距离。
Levenshtein距离可以由使用动态规划找到，将两个字符串的所有前缀之间的距离存储在一个矩阵中，然后追溯您的步骤，以便在矩阵的每一行找到这是最优的操作(达到该操作所需的操作最少)。
@IvayloStrandjev提出的最长增长子序列算法与最长的公共子序列问题有关，该问题又与编辑距离相关，后者是一种只允许插入和替换的替代度量。它在太空中可能更有表现力，因为它利用了一个序列必须排序的事实；我只是想提供一个我觉得更容易理解的替代答案。
下面是完整矩阵Levenshtein算法在Python中的一个实现，如上面链接的维基百科页面(最初在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 2Stack Overflow用户
发布于 2014-02-17 21:57:18
这在很大程度上取决于一些没有说明的问题参数。首先，什么举措是合法的？只有相邻的元素交换？有任意删除和插入吗？第二，您只是需要移动的数量，还是需要一个特定移动的列表来执行？这就产生了不同的算法：
- 只有相邻的掉期-这就是所谓的倒排计数，如果你只关心最小的数。
- 删除、非相邻交换等等- 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是一个明确的选择。
Stack Overflow用户
发布于 2014-02-17 20:16:44
执行循环排序并计算移动次数。那肯定是最小的数目。
https://stackoverflow.com/questions/21452645
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号