go - 出乎意料的是我的代码基于 `map[int][][]int` 的结果

Question

我在 Linux(Ubuntu 1604)/amd64 上的 Go 版本 1.7.4、1.8、1.8.1 中运行我的代码

我正在尝试使用结构 m := map[int][][]int 编写代码来执行以下操作。

对于数组 numbers := []int{0,1,2,3,4}，让 m[0] = [][]int{[]int{ 0}, []int{1}, []int{2}, []int{3}, []int{4}},并将 numbers 中的数字 n 附加到所有 m[i] 列表中，然后将 m[1] 作为下面。

m[1] -> [[0,1], [0,2],..,[0,4],[1,2],[1,3],..,[ 1,4],...,,[2,3],[2,4],[3,4]]

等等 m[2] -> [[0,1,2],[0,1,3],.....], m[3 ], m[4]

这是我的代码。

package main

import (
    "fmt"
)

func main() {
    n := 5
    m := make(map[int][][]int)
    list := make([][]int, 0)
    for i := 0; i < n; i++ {
        list = append(list, []int{i})
    }
    m[0] = list
    fmt.Println(m)
    for level := 1; level < n; level++ {
        newlist := make([][]int, 0)
        for _, lst := range m[level-1] {
            for i := 0; i < n; i++ {
                if i > lst[len(lst)-1] {
                    newlst := append(lst, i)
                    newlist = append(newlist, newlst)
                    fmt.Println(level, ":", lst, i, "->", newlst, "=>", newlist)
                }
            }
        }
        m[level] = newlist
    }
    fmt.Println(m)
}

输出如下。

map[0:[[0] [1] [2] [3] [4]]]
1 : [0] 1 -> [0 1] => [[0 1]]
1 : [0] 2 -> [0 2] => [[0 1] [0 2]]
1 : [0] 3 -> [0 3] => [[0 1] [0 2] [0 3]]
1 : [0] 4 -> [0 4] => [[0 1] [0 2] [0 3] [0 4]]
1 : [1] 2 -> [1 2] => [[0 1] [0 2] [0 3] [0 4] [1 2]]
1 : [1] 3 -> [1 3] => [[0 1] [0 2] [0 3] [0 4] [1 2] [1 3]]
1 : [1] 4 -> [1 4] => [[0 1] [0 2] [0 3] [0 4] [1 2] [1 3] [1 4]]
1 : [2] 3 -> [2 3] => [[0 1] [0 2] [0 3] [0 4] [1 2] [1 3] [1 4] [2 3]]
1 : [2] 4 -> [2 4] => [[0 1] [0 2] [0 3] [0 4] [1 2] [1 3] [1 4] [2 3] [2 4]]
1 : [3] 4 -> [3 4] => [[0 1] [0 2] [0 3] [0 4] [1 2] [1 3] [1 4] [2 3] [2 4] [3 4]]
2 : [0 1] 2 -> [0 1 2] => [[0 1 2]]
2 : [0 1] 3 -> [0 1 3] => [[0 1 2] [0 1 3]]
2 : [0 1] 4 -> [0 1 4] => [[0 1 2] [0 1 3] [0 1 4]]
2 : [0 2] 3 -> [0 2 3] => [[0 1 2] [0 1 3] [0 1 4] [0 2 3]]
2 : [0 2] 4 -> [0 2 4] => [[0 1 2] [0 1 3] [0 1 4] [0 2 3] [0 2 4]]
2 : [0 3] 4 -> [0 3 4] => [[0 1 2] [0 1 3] [0 1 4] [0 2 3] [0 2 4] [0 3 4]]
2 : [1 2] 3 -> [1 2 3] => [[0 1 2] [0 1 3] [0 1 4] [0 2 3] [0 2 4] [0 3 4] [1 2 3]]
2 : [1 2] 4 -> [1 2 4] => [[0 1 2] [0 1 3] [0 1 4] [0 2 3] [0 2 4] [0 3 4] [1 2 3] [1 2 4]]
2 : [1 3] 4 -> [1 3 4] => [[0 1 2] [0 1 3] [0 1 4] [0 2 3] [0 2 4] [0 3 4] [1 2 3] [1 2 4] [1 3 4]]
2 : [2 3] 4 -> [2 3 4] => [[0 1 2] [0 1 3] [0 1 4] [0 2 3] [0 2 4] [0 3 4] [1 2 3] [1 2 4] [1 3 4] [2 3 4]]
3 : [0 1 2] 3 -> [0 1 2 3] => [[0 1 2 3]]
3 : [0 1 2] 4 -> [0 1 2 4] => [[0 1 2 4] [0 1 2 4]]
3 : [0 1 3] 4 -> [0 1 3 4] => [[0 1 2 4] [0 1 2 4] [0 1 3 4]]
3 : [0 2 3] 4 -> [0 2 3 4] => [[0 1 2 4] [0 1 2 4] [0 1 3 4] [0 2 3 4]]
3 : [1 2 3] 4 -> [1 2 3 4] => [[0 1 2 4] [0 1 2 4] [0 1 3 4] [0 2 3 4] [1 2 3 4]]
map[4:[] 0:[[0] [1] [2] [3] [4]] 1:[[0 1] [0 2] [0 3] [0 4] [1 2] [1 3] [1 4] [2 3] [2 4] [3 4]] 2:[[0 1 2] [0 1 3] [0 1 4] [0 2 3] [0 2 4] [0 3 4] [1 2 3] [1 2 4] [1 3 4] [2 3 4]] 3:[[0 1 2 4] [0 1 2 4] [0 1 3 4] [0 2 3 4] [1 2 3 4]]]

这里的问题。

3 : [0 1 2] 3 -> [0 1 2 3] => [[0 1 2 3]]
3 : [0 1 2] 4 -> [0 1 2 4] => [[0 1 2 4] [0 1 2 4]]           
3 : [0 1 3] 4 -> [0 1 3 4] => [[0 1 2 4] [0 1 2 4] [0 1 3 4]]
3 : [0 2 3] 4 -> [0 2 3 4] => [[0 1 2 4] [0 1 2 4] [0 1 3 4] [0 2 3 4]]
3 : [1 2 3] 4 -> [1 2 3 4] => [[0 1 2 4] [0 1 2 4] [0 1 3 4] [0 2 3 4] [1 2 3 4]]

正确的输出应该是:

3 : [0 1 2] 3 -> [0 1 2 3] => [[0 1 2 3]]
3 : [0 1 2] 4 -> [0 1 2 4] => [[0 1 2 **3**] [0 1 2 4]]           
3 : [0 1 3] 4 -> [0 1 3 4] => [[0 1 2 **3**] [0 1 2 4] [0 1 3 4]]
3 : [0 2 3] 4 -> [0 2 3 4] => [[0 1 2 **3**] [0 1 2 4] [0 1 3 4] [0 2 3 4]]
3 : [1 2 3] 4 -> [1 2 3 4] => [[0 1 2 **3**] [0 1 2 4] [0 1 3 4] [0 2 3 4] [1 2 3 4]]

我不知道为什么，但我认为这可能是 Go 编译器或运行时的错误。

问题的原因是什么？可能是 Go 错误或只是我的代码错误。如果 Go 或我的代码有错误，如何解决？干杯!

Answer 1

在这段代码中，你的 slice 可能会互相使用别名:

newlist := make([][]int, 0)
for _, lst := range m[level-1] {
    for i := 0; i < n; i++ {
        if i > lst[len(lst)-1] {
            newlst := append(lst, i)
            newlist = append(newlist, newlst)

您将 i 附加到先前计算的 slice ，这可能会也可能不会重新分配底层数组。如果不是，每个 newlst 都会重用相同的底层数组，因此在早期版本的 newlst 中，值会被以后版本的 newlst 覆盖.

您需要通过复制数据强制新 slice 使用新的底层数组:

newlst := append([]int{}, lst...)
newlst = append(newlst, i)

Here's a playground version of the fixed code.