我正在尋找一種通用算法來找到兩個有序列表之間的最小差異。我在 Go 中需要它，所以讓我們假設它們是字符串切片。列表示例：list := []string{ "Anna", "Mike", "Simon", "Jerry", "Louisa", "Mary",}請注意，此列表中的元素是唯一的。第二個列表將是此列表的更改版本。更改可能包括以下任何一種情況，單獨或組合：一個（或多個）列表元素向上或向下移動一個或幾個位置；兩個元素交換位置；一個新元素替換了一個舊元素。作為比較的結果，我想要的是一組最小的更改，這些更改需要應用于第一個列表以獲得第二個列表。然后我會使用這些數據來標記列表中的更改。例如，我想產生這樣的輸出：AnnaMike↑LouisaSimonJerryMary這說明在新的榜單中，“路易莎”已經上移了。我還想知道“路易莎”已經上升了2 個位置，但我不需要在我的輸出中顯示它。對我來說重要的是“Simon”和“Jerry”的位置也發生了變化，但列表之間的整體差異只能用“Louisa”向上移動2個位置來描述，而且這樣的描述更短，所以我認為它是最小的這就是我想要得到的。有沒有可以解決問題的軟件包，或者可能是已知的算法？如果它很重要，那么列表的長度在我的情況下不會改變。
1 回答
喵喵時光機
TA貢獻1846條經驗 獲得超7個贊
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 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)返回一個字符串列表，以下列方式說明兩個列表之間的變化：
它具有與更新列表相同的順序和組成；
將前綴“*”添加到更新列表的所有新元素；
將前綴“↑”添加到需要向上移動（朝向列表開頭）以將舊列表轉換為更新列表的元素；
需要向下移動的元素添加前綴“↓”；
它優先考慮“向上”移位（如果兩個相鄰元素交換位置）。
讓我們使用以下列表來測試它：
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
這是一個工作的游樂場示例。
我很確定它遠非完美，但它肯定會滿足我的需求。
- 1 回答
- 0 關注
- 123 瀏覽
添加回答
舉報
0/150
提交
取消