算法：两个有序列表之间的区别，按顺序和组成

Question

我正在寻找一种通用算法来找到两个有序列表之间的最小差异。

我在 Go 中需要它，所以让我们假设它们是字符串切片。列表示例：

list := []string{

    "Anna",

    "Mike",

    "Simon",

    "Jerry",

    "Louisa",

    "Mary",

}

请注意，此列表中的元素是唯一的。

第二个列表将是此列表的更改版本。更改可能包括以下任何一种情况，单独或组合：

一个（或多个）列表元素向上或向下移动一个或几个位置；

两个元素交换位置；

一个新元素替换了一个旧元素。

作为比较的结果，我想要的是一组最小的更改，这些更改需要应用于第一个列表以获得第二个列表。然后我会使用这些数据来标记列表中的更改。例如，我想产生这样的输出：

Anna

Mike

↑Louisa

Simon

Jerry

Mary

这说明在新的榜单中，“路易莎”已经上移了。我还想知道“路易莎”已经上升了2 个位置，但我不需要在我的输出中显示它。

对我来说重要的是“Simon”和“Jerry”的位置也发生了变化，但列表之间的整体差异只能用“Louisa”向上移动2个位置来描述，而且这样的描述更短，所以我认为它是最小的这就是我想要得到的。

有没有可以解决问题的软件包，或者可能是已知的算法？如果它很重要，那么列表的长度在我的情况下不会改变。

Answer 1

Volker和torek，感谢您的评论，我发现它们与问题最相关。为题外话道歉，我还没有太多在 StackOverflow 上提问的经验。torek引用的文章重点是设计一种可实现最高效率的算法。这确实是一项了不起的成就，但在我的特定应用程序中，我将使用此算法处理仅包含 10 个项目的列表，并且仅在几个小时内执行一次，因此我不需要它来获得一流的效率。因此，我对如何做到这一点有了一个相当简单的想法，而且它似乎有效。这个想法是计算所有元素的新旧位置之间的差异，找到具有最大偏移的元素，在输出报告中标记它是如何移动的，然后将其移动到新位置。然后重复它，直到列表相同。在此操作之前，应解决列表组成的差异。我不能保证它在大列表上完全按预期工作，它们之间有很多差异，但我需要它来处理相对较短的列表，只有 1-2 处更改，所以它应该对我有用。这是一个示例代码：// diff describes how an updated position of an element is different from an old one// it's either a new element, or it's shifted by "shift" in "direction", or position didn't changetype diff struct {&nbsp; &nbsp; shift int&nbsp; &nbsp; direction direction&nbsp; &nbsp; isNew bool}type direction intconst (&nbsp; &nbsp; up = direction(-1)&nbsp; &nbsp; down = direction(1)&nbsp; &nbsp; none = direction(0))func hasShifts(shifts []diff) bool {&nbsp; &nbsp; for _, d := range shifts {&nbsp; &nbsp; &nbsp; &nbsp; if d.shift != 0 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return true&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return false}func diffs(old, updated []string) (shifts []diff) {&nbsp; &nbsp; for i, newEl := range updated {&nbsp; &nbsp; &nbsp; &nbsp; for j, oldEl := range old {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if newEl == oldEl {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; var dir direction&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; switch {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; case i < j:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dir = up&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; case i > j:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dir = down&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; default:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dir = none&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; shifts = append(shifts, diff{int(math.Abs(float64(i-j))), dir, false})&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; if len(shifts) < i+1 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; shifts = append(shifts, diff{isNew: true})&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return}func move(list *[]string, position, shift int, dir direction) {&nbsp; &nbsp; for i := position; i != position + shift * int(dir); i += int(dir) {&nbsp; &nbsp; &nbsp; &nbsp; (*list)[i], (*list)[i+int(dir)] = (*list)[i+int(dir)], (*list)[i]&nbsp; &nbsp; }}func compare(old, updated []string) (report []string) {&nbsp; &nbsp; report = append([]string{}, updated...)&nbsp; &nbsp; // first, find and mark updated elements; add them to the old list&nbsp; &nbsp; shifts := diffs(old, updated)&nbsp; &nbsp; for i, d := range shifts {&nbsp; &nbsp; &nbsp; &nbsp; if d.isNew {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; old = append(old[:i], append(updated[i:i+1], old[i:]...)...)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; report[i] = "*" + report[i]&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; // remove elements of the old list that aren't present in the updated&nbsp; &nbsp; shifts = diffs(updated, old) // reversed&nbsp; &nbsp; n := 0&nbsp; &nbsp; for i, d := range shifts {&nbsp; &nbsp; &nbsp; &nbsp; if !d.isNew {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; old[n] = old[i]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; n++&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; old = old[:n]&nbsp; &nbsp; // until lists are identical&nbsp; &nbsp; shifts = diffs(old, updated)&nbsp; &nbsp; for hasShifts(shifts) {&nbsp; &nbsp; &nbsp; &nbsp; // find an element with the largest shift&nbsp; &nbsp; &nbsp; &nbsp; highest := 0&nbsp; &nbsp; &nbsp; &nbsp; for i, d := range shifts {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if d.shift > shifts[highest].shift || (d.shift == shifts[highest].shift && d.direction == up) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; highest = i&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; // mark in report how this element shifted&nbsp; &nbsp; &nbsp; &nbsp; if shifts[highest].direction == up {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; report[highest] = "↑" + report[highest]&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; report[highest] = "↓" + report[highest]&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; // move this element in the old list to its updated place&nbsp; &nbsp; &nbsp; &nbsp; for i, oldEl := range old {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if oldEl == updated[highest] {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; move(&old, i, shifts[highest].shift, shifts[highest].direction)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; // update diffs&nbsp; &nbsp; &nbsp; &nbsp; shifts = diffs(old, updated)&nbsp; &nbsp; }&nbsp; &nbsp; return}该函数compare(old, updated)返回一个字符串列表，以下列方式说明两个列表之间的变化：它具有与更新列表相同的顺序和组成；将前缀“*”添加到更新列表的所有新元素；将前缀“↑”添加到需要向上移动（朝向列表开头）以将旧列表转换为更新列表的元素；需要向下移动的元素添加前缀“↓”；它优先考虑“向上”移位（如果两个相邻元素交换位置）。让我们使用以下列表来测试它：var (&nbsp; &nbsp; old = []string{&nbsp; &nbsp; &nbsp; &nbsp; "first",&nbsp; &nbsp; &nbsp; &nbsp; "second",&nbsp; &nbsp; &nbsp; &nbsp; "third",&nbsp; &nbsp; &nbsp; &nbsp; "fourth",&nbsp; &nbsp; &nbsp; &nbsp; "fifth",&nbsp; &nbsp; &nbsp; &nbsp; "sixth",&nbsp; &nbsp; &nbsp; &nbsp; "seventh",&nbsp; &nbsp; &nbsp; &nbsp; "eighth",&nbsp; &nbsp; &nbsp; &nbsp; "ninth",&nbsp; &nbsp; &nbsp; &nbsp; "tenth",&nbsp; &nbsp; }&nbsp; &nbsp; updated = []string{&nbsp; &nbsp; &nbsp; &nbsp; "eighth",&nbsp; &nbsp; &nbsp; &nbsp; "second",&nbsp; &nbsp; &nbsp; &nbsp; "third",&nbsp; &nbsp; &nbsp; &nbsp; "first",&nbsp; &nbsp; &nbsp; &nbsp; "fourth",&nbsp; &nbsp; &nbsp; &nbsp; "new",&nbsp; &nbsp; &nbsp; &nbsp; "sixth",&nbsp; &nbsp; &nbsp; &nbsp; "seventh",&nbsp; &nbsp; &nbsp; &nbsp; "tenth",&nbsp; &nbsp; &nbsp; &nbsp; "ninth",&nbsp; &nbsp; })结果将是：↑eighthsecondthird↓firstfourth*newsixthseventh↑tenthninth这是一个工作的游乐场示例。我很确定它远非完美，但它肯定会满足我的需求。