CODEWITHSUNDEEP
algorithmgo
maxm
maxm

Reputation: 3667

Similar Go functions appending strings and arrays do not behave as expected

I have two Go functions:

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?

Upvotes: 1

Views: 65

Answers (1)

tomasz
tomasz

Reputation: 13062

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:

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

https://blog.golang.org/slices

Upvotes: 2

Related Questions