英文:
Similar Go functions appending strings and arrays do not behave as expected
问题
我有两个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
我猜测我可能忽略了一些关于追加数组的细微差别。我似乎无法弄清楚问题所在。你有什么想法吗？
英文:
I have two Go functions:
<!-- language: lang-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:]),
)
}
}
}
The first takes an array of ints, the second takes a string. They both then calculate all permutations of the array, or the string.
I can run them like so:
permutation([]int{}, []int{1, 2, 3})
perms("", "123")
Their output is not the same:
$ 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
I guess there is some nuance to appending arrays that I am missing. I can't seem to figure it out. Any idea what's going on?
答案1
得分: 2
str1+str2返回一个新的字符串（在内存中与原字符串无关），但append的行为不同。例如，append(str[0:i], str[i+1:]...)会破坏str的原始内容，用str[i+1:]覆盖str[i:]。这是因为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)
}
有关切片和append机制的更多信息，请参考以下链接：
英文:
While str1+str2 does return new (unrelated in terms of memory) string, append doesn't behave this way. For example append(str[0:i], str[i+1:]...) will destroy original content of str, overwriting str[i:] with str[i+1:]. This is because str[0:i] will have capacity to append str[i+1:] without allocating new buffer.
The solution would be to create a completely new array in every iteration. At least for str, as append(prefix, str[i]) is immune to this problem. For example:
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
More about slices and mechanism of append:
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论