这是一个非常简单的程序,它枚举了元素列表的所有可能组合。问题是,当元素数量等于或大于 5 时,会生成虚假结果。
package main
import "fmt"
func Combination(choices []int) [][]int {
result := [][]int{}
if len(choices) == 0 {
result = append(result, choices)
return result
} else {
head := choices[0]
tail := choices[1:]
for _, combo := range Combination(tail) {
result = append(result, combo)
result = append(result, append(combo, head))
}
}
return result
}
func main() {
for idx, c := range Combination([]int{0, 1, 2, 3, 4}) {
fmt.Println(idx, c)
}
}
结果是
...
30 [4 3 2 0]
31 [4 3 2 0 0]
我已经花了很长时间但仍然一无所知。我怀疑这可能是切片的长度、盖子怪异,但我不确定。
谢谢
它应该生成所有可能的元素组合。
行
result = append(result, append(combo, head))
修改 combo
的原因是,它会导致组合被损坏的不良副作用。
由于 go 中的切片是引用类型,因此
append
可以就地修改其参数或返回其参数的副本以及附加条目
a := []int{1, 2, 3}
// return a copy of its argument
a = append(a, 4)
fmt.Println(a)
// modify its argument in-place
_ = append(a[:3], 5)
fmt.Println(a)
所以正确的方法是:
package main
import "fmt"
func Combination(choices []int) [][]int {
result := [][]int{}
if len(choices) == 0 {
result = append(result, []int{})
return result
} else {
head := choices[0]
tail := choices[1:]
for _, combo := range Combination(tail) {
result = append(result, combo)
// Create a new combination
newCombo := make([]int, len(combo))
// Copy combo elemtnets to newCombo
copy(newCombo, combo)
// Adding head to a new slice
newCombo = append(newCombo, head)
result = append(result, newCombo)
}
}
return result
}
func main() {
for idx, c := range Combination([]int{0, 1, 2, 3, 4}) {
fmt.Println(idx, c)
}
}