I was trying to implement Heap's Algorithm in go using channels. The code below is working fine when just printing the slices on the screen, but when using channels to delivery the arrays to a for/range loop on main function some unexpected behaviour occurs and the slices/arrays are printed in duplicity and not all permutations are sent. I thought that maybe i'm closing the channel earlier than the main function is able to print the results but i wouldn't expect that double print. Why is this happening and how can i make it work.
package main
import "fmt"
func perm(a []int64) {
var n = len(a)
var c = make([]int, n)
fmt.Println(a)
i := 0
for i < n {
if c[i] < i {
if i%2 == 0 {
a[0], a[i] = a[i], a[0]
} else {
a[c[i]], a[i] = a[i], a[c[i]]
}
fmt.Println(a)
c[i]++
i = 0
} else {
c[i] = 0
i++
}
}
}
func permch(a []int64, ch chan<- []int64) {
var n = len(a)
var c = make([]int, n)
ch <- a
i := 0
for i < n {
if c[i] < i {
if i%2 == 0 {
a[0], a[i] = a[i], a[0]
} else {
a[c[i]], a[i] = a[i], a[c[i]]
}
ch <- a
c[i]++
i = 0
} else {
c[i] = 0
i++
}
}
close(ch)
}
func main() {
var i = []int64{1, 2, 3}
fmt.Println("Without Channels")
perm(i)
ch := make(chan []int64)
go permch(i, ch)
fmt.Println("With Channels")
for slc := range ch {
fmt.Println(slc)
}
}
It looks like permch is modifying a at the same time as main is printing it, so your output is garbled.
I can think of three easy fixes:
a with a mutex.a on the channel:permch can continue. (don't really recommend this, but it works).Number 2 is pretty simple:
a2 := make([]int64, len(a))
copy(a2,a)
ch <- a2
and is what I would recommend.
For #1, just declare a var m sync.Mutex as a package variable and Lock is anytime you read or modify a. This is a race condition though between the reader and the next modification, as you pointed out, so it probably isn't a good solution after all.
Your problem is that slices are reference types, and are being accessed in multiple goroutines. In perm, you're printing a directly as you finish processing it at each step. In permch, you're sending a over the channel, but then immediate starting to modify it again. Since each slice sent over the channel refers to the same underlying array, you have a race condition as to whether your next loop iteration alters a or your Println() call in main gets to that array first.
In general, if you're running into unexpected behavior in any program using goroutines, you probably have a race condition. Run the program with the -race flag to see where.
Edit: also, closing a channel has no effect on a routine reading from the channel. A channel can continue to be read until its buffer is empty, at which point it will start returning the zero value for that type instead. Range loops over a channel will only terminate once the channel is closed and its buffer is empty.