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

Question

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

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

list := []string{
    "Anna",
    "Mike",
    "Simon",
    "Jerry",
    "Louisa",
    "Mary",
}

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

第二个列表是这个列表的修改版本。更改可能包括以下任何情况，单独或合并：

一个（或多个）列表元素向上或向下移动一个或几个位置；
两个元素互换位置；
一个新元素替换了一个旧元素。

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

Anna
Mike
↑Louisa
Simon
Jerry
Mary

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

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

有没有可以解决这个问题的软件包，或者已知的算法？如果它有任何重要性，列表的长度在我的情况下不会改变。

Answer 1

Volker 和 torek，感谢您的评论，我发现它们与问题最相关。抱歉跑题了，我还没有太多在 Whosebug 上提问的经验。

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 change
type diff struct {
    shift int
    direction direction
    isNew bool
}

type direction int
const (
    up = direction(-1)
    down = direction(1)
    none = direction(0)
)

func hasShifts(shifts []diff) bool {
    for _, d := range shifts {
        if d.shift != 0 {
            return true
        }
    }
    return false
}

func diffs(old, updated []string) (shifts []diff) {
    for i, newEl := range updated {
        for j, oldEl := range old {
            if newEl == oldEl {
                var dir direction
                switch {
                case i < j:
                    dir = up
                case i > j:
                    dir = down
                default:
                    dir = none
                }
                shifts = append(shifts, diff{int(math.Abs(float64(i-j))), dir, false})
                break
            }
        }
        if len(shifts) < i+1 {
            shifts = append(shifts, diff{isNew: true})
        }
    }
    return
}

func move(list *[]string, position, shift int, dir direction) {
    for i := position; i != position + shift * int(dir); i += int(dir) {
        (*list)[i], (*list)[i+int(dir)] = (*list)[i+int(dir)], (*list)[i]
    }
}

func compare(old, updated []string) (report []string) {
    report = append([]string{}, updated...)

    // first, find and mark updated elements; add them to the old list
    shifts := diffs(old, updated)
    for i, d := range shifts {
        if d.isNew {
            old = append(old[:i], append(updated[i:i+1], old[i:]...)...)
            report[i] = "*" + report[i]
        }
    }

    // remove elements of the old list that aren't present in the updated
    shifts = diffs(updated, old) // reversed
    n := 0
    for i, d := range shifts {
        if !d.isNew {
            old[n] = old[i]
            n++
        }
    }
    old = old[:n]

    // until lists are identical
    shifts = diffs(old, updated)
    for hasShifts(shifts) {
        // find an element with the largest shift
        highest := 0
        for i, d := range shifts {
            if d.shift > shifts[highest].shift || (d.shift == shifts[highest].shift && d.direction == up) {
                highest = i
            }
        }

        // mark in report how this element shifted
        if shifts[highest].direction == up {
            report[highest] = "↑" + report[highest]
        } else {
            report[highest] = "↓" + report[highest]
        }

        // move this element in the old list to its updated place
        for i, oldEl := range old {
            if oldEl == updated[highest] {
                move(&old, i, shifts[highest].shift, shifts[highest].direction)
                break
            }
        }

        // update diffs
        shifts = diffs(old, updated)
    }
    return
}

函数 compare(old, updated) returns 一个字符串列表，以下列方式说明两个列表之间的变化：

它与更新列表具有相同的顺序和组成；
更新列表的所有新元素都添加了前缀“*”；
在需要向上移动（向列表的开头）的元素添加前缀“↑”以将旧列表转换为更新的列表；
需要下移的元素加前缀“↓”；
它优先考虑“向上”移动（如果两个相邻元素交换位置）。

让我们使用以下列表对其进行测试：

var (
    old = []string{
        "first",
        "second",
        "third",
        "fourth",
        "fifth",
        "sixth",
        "seventh",
        "eighth",
        "ninth",
        "tenth",
    }
    updated = []string{
        "eighth",
        "second",
        "third",
        "first",
        "fourth",
        "new",
        "sixth",
        "seventh",
        "tenth",
        "ninth",
    }
)

结果将是：

↑eighth
second
third
↓first
fourth
*new
sixth
seventh
↑tenth
ninth

这是一个有效的 go playground example。

我很确定它远非完美，但它肯定会满足我的需要。

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

Algorithm: Difference between two ordered lists, by order and composition

algorithm

go

difference