The following code implements the yield pattern in golang. As an experiment I was implementing an all permutations
generator. However, when I return the slice A
to channel, if I do not create a new copy of the array I get an incorrect result.
Please see the code around "???
". Can someone explain what happens under the covers here? I thought that since the channel is not buffered, I was guaranteed that after publishing the array's slice to the channel I was ensured that the result would be consumed before continuing.
package main
import (
"fmt"
)
func swap(A []int, i int, j int) {
t := A[i]
A[i] = A[j]
A[j] = t
}
func recurse(A []int, c chan []int, depth int) {
if depth == len(A) {
// ??? Why do I need to copy the data?
// If I do c <- A I get an incorrect answer.
ra := make([]int, len(A))
copy(ra, A)
c <- ra
return
}
for i := depth; i < len(A); i++ {
swap(A, depth, i)
recurse(A, c, depth+1)
swap(A, depth, i)
}
}
func yieldPermutations(A []int, c chan []int) {
recurse(A, c, 0)
close(c)
}
func main() {
A := []int{1, 2, 3}
c2 := make(chan []int)
go yieldPermutations(A, c2)
for v := range c2 {
fmt.Println(v)
}
}
If I do not copy the data, I get the following result:
[1 3 2]
[1 3 2]
[2 3 1]
[2 3 1]
[3 1 2]
[3 1 2]
Obviously, the correct result (which we get with data copy) is:
[1 2 3]
[1 3 2]
[2 1 3]
[2 3 1]
[3 2 1]
[3 1 2]