algorithm - 附加字符串和数组的类似 Go 函数未按预期运行

Question

我有两个 Go 函数:

func permutation(prefix, str []int) {
    n := len(str)
    if n == 0 {
        fmt.Println(prefix)
    } else {
        for i := 0; i < n; i++ {
            permutation(
                append(prefix, str[i]),
                append(str[0:i], str[i+1:]...),
            )
        }
    }
}

func perms(prefix, str string) {
    n := len(str)
    if n == 0 {
        fmt.Println(prefix)
    } else {
        for i := 0; i < n; i++ {
            perms(
                prefix+string(str[i]),
                string(str[0:i])+string(str[i+1:]),
            )
        }
    }
}

第一个接受一个整数数组，第二个接受一个字符串。然后他们都计算数组或字符串的所有排列。

我可以这样运行它们:

permutation([]int{}, []int{1, 2, 3})
perms("", "123")

它们的输出不一样:

$ go run main.go
[1 2 3]
[1 3 3]
[3 3 3]
[3 3 3]
[3 3 3]
[3 3 3]
123
132
213
231
312
321

我想追加我遗漏的数组有一些细微差别。我似乎无法弄清楚。知道发生了什么事吗？

Answer 1

虽然 str1+str2 确实返回新的(在内存方面不相关)字符串，但 append 不会以这种方式运行。例如append(str[0:i], str[i+1:]...)会破坏str的原始内容，覆盖str[i :] 与 str[i+1:]。这是因为 str[0:i] 可以在不分配新缓冲区的情况下追加 str[i+1:]。

解决方案是在每次迭代中创建一个全新的数组。至少对于 str，因为 append(prefix, str[i]) 不受此问题的影响。例如:

for i := 0; i < n; i++ {
    var s []int
    s = append(s, str[0:i]...)
    s = append(s, str[i+1:]...)
    permutation(append(prefix, str[i]), s)
}

https://play.golang.org/p/lXwu39AA0V

关于 slice 和追加机制的更多信息:

http://blog.golang.org/go-slices-usage-and-internals

https://blog.golang.org/slices