Code to generate powerset in Golang gives wrong result

Question

Next code in Golang to generate powerset produces wrong result on input {"A", "B", "C", "D", "E"}. I see [A B C E E] as the last generated set.

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
}

How to fix it? How to write it idiomatically in Go?

eugenioy · Accepted Answer · 2017-07-23T18:38:22.177

The problem with your program is not the algorithm itself but this line:

newSet := append(existingSet, element)

You should not append and assign to a different variable.

As the documentation states (emphasis mine), "The append built-in function appends elements to the end of a slice. If it has sufficient capacity, the destination is resliced to accommodate the new elements. If it does not, a new underlying array will be allocated.".

So, there might be cases where newSet := append(existingSet, element) will actually modify existingSet itself, which would break your logic.

If you change that to instead create a new array and append to that one, it works as you expect it.

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

score 1 · Answer 2 · answered Jul 23 '17 at 18:22

For instance, you can use algorithm like this one: 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
}

score 1 · Answer 3 · answered Jul 23 '17 at 18:30

Elaborating on @eugenioy's answer.
Look at this thread. Here is a working example : 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
}

Thanks for a link to that thread on Google Groups. I shouldn't assume any behaviour by function's name. — TohaSt, Jul 23 '17 at 21:09

Code to generate powerset in Golang gives wrong result

3 Answers3