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

Question

I ran my code in Go versions 1.7.4, 1.8, 1.8.1 on Linux(Ubuntu 1604)/amd64

I'm trying to use a structure m := map[int][][]int to write a code to do something below.

For an array numbers := []int{0,1,2,3,4}, let m[0] = [][]int{[]int{0}, []int{1}, []int{2}, []int{3}, []int{4}}, and append a number n within numbers to all list of m[i], then m[1] as below.

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

and so on for m[2] -> [[0,1,2],[0,1,3],.....], m[3], m[4]

Here is my code.

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)
}

And the output as below.

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]]]

The issue at here.

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]]

The correct output should be:

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]]

I don't know why, but I think it may be a bug of Go compiler or runtime.

What reason of the issue? Maybe a Go bug or just my code mistake. How to solve it if a bug for Go or my code? Cheers!

Answer 1

In this code, your slices may alias each other:

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)

You're appending i to a previously computed slice, which may or may not reallocate the underlying array. When it doesn't, each newlst reuses the same underlying array, so in earlier versions of newlst, values are overwritten by later versions of newlst.

You need to force the new slices to use new underlying arrays by copying the data:

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

Here's a playground version of the fixed code.