在 Golang 中生成功率集的代码给出了错误的结果

Question

Golang 中生成功率集的下一个代码在输入{"A", "B", "C", "D", "E"}上产生错误的结果。我认为[A B C E E]是最后一个生成的集合。

package main
import (
"fmt"
)
func main() {
for _, s := range PowerSet([]string{"A", "B", "C", "D", "E"}) {
fmt.Println(s)  
}   
}
func PowerSet(set []string) [][]string {
var powerSet [][]string
powerSet = append(powerSet, make([]string, 0))
for _, element := range set {
var moreSets [][]string
for _, existingSet := range powerSet {
newSet := append(existingSet, element)
moreSets = append(moreSets, newSet)
}
powerSet = append(powerSet, moreSets...)
}
return powerSet
}

如何解决？如何在围棋中习惯性地写它？

Answer 1

程序的问题不在于算法本身，而在于这一行：

newSet := append(existingSet, element)

不应append并分配给其他变量。

正如文档所述(强调我的(，"追加内置函数将元素附加到切片的末尾。如果它有足够的容量，则会重新切片目标以容纳新元素。如果没有，将分配一个新的底层阵列。

因此，在某些情况下，newSet := append(existingSet, element)实际上会修改existingSet本身，这会破坏您的逻辑。

如果您将其更改为创建一个新数组并附加到该数组，它将按预期工作。

newSet := make([]string, 0)
newSet = append(newSet, existingSet...) 
newSet = append(newSet, element)

Answer 2

例如，您可以使用这样的算法：https://stackoverflow.com/a/2779467/3805062。

func PowerSet(original []string) [][]string {
powerSetSize := int(math.Pow(2, float64(len(original))))
result := make([][]string, 0, powerSetSize)
var index int
for index < powerSetSize {
var subSet []string
for j, elem := range original {
if index& (1 << uint(j)) > 0 {
subSet = append(subSet, elem)
}
}
result = append(result, subSet)
index++
}
return result
}

Answer 3

详细阐述@eugenioy的答案。
看看这个线程。这是一个工作示例： https://play.golang.org/p/dzoTk1kimf

func copy_and_append_string(slice []string, elem string) []string {
// wrong: return append(slice, elem)
return append(append([]string(nil), slice...), elem)
}
func PowerSet(s []string) [][]string {
if s == nil {
return nil
}
r := [][]string{[]string{}}
for _, es := range s {
var u [][]string
for _, er := range r {
u = append(u, copy_and_append_string(er, es))
}
r = append(r, u...)
}
return r
}