Goroutines seem to be interrupted despite the presence of a WaitGroup

I have a problem with goroutines not concluding in spite of a WaitGroup. In the code appended, you can see an implementation of Heap's algorithm for permutations. I wanted to speed it up, and so I created a goroutine for every possible first number and thereby decreased the permutations per goroutine to (n-1)!. In total, I should still have n! permutations (n*(n-1)! = n!), but my main routine seems to exit before the sub routines are finished. I then tried tracking the executed permutations. Against my belief, the number of permutations executed isn't constant, but always a bit (for low n) or very much (for large n) under n!.

For example, the permutations for n=4 is 24 every time, that is 4! and thereby all goroutines have finished. If I have a higher number like n=8, I get a value around 13500 and not the expected 40000 = 8!.

Where does this behavior come from? How can I ensure that all my goroutines have finished before the main program exits?

package main

import (
	"fmt"
	"sync"
)

var wg sync.WaitGroup
var permutations int

func main() {

	n := 9

	wg.Add(n)

	for i := 0; i < n; i++ {

		var arr []int
		for j := 0; j < n; j++ {
			if i != j {
				arr = append(arr, j+1)
			}
		}
		go threadFunction(n-1, i+1, arr)
	}

	wg.Wait()

	fmt.Println(permutations)
}

func threadFunction(k int, suffix int, arr []int) {

	defer wg.Done()

	heapPermutation(k, suffix, arr)
}

func heapPermutation(k int, prefix int, arr []int) {

	if k == 1 {
		arr = append(arr, prefix)
		// fmt.Println(arr)
		permutations++
	} else {
		heapPermutation(k-1, prefix, arr)

		for i := 0; i < k-1; i++ {
			if k%2 == 0 {
				arr[i], arr[k-1] = arr[k-1], arr[i]
			} else {
				arr[0], arr[k-1] = arr[k-1], arr[0]
			}
			heapPermutation(k-1, prefix, arr)
		}
	}
}

(The same behavior can be easily achieved, e.g. on https://go.dev/play/, thus it is very much reproducible.)

In your code, goroutines access permutations variable concurrently. When you increase value of n, the workload increases and it becomes the issue leading to an unexpected result.

You can use a mutex, it will ensure that only one goroutine can access the permutations at the time.

package main
import (
"fmt"
"sync"
)
var wg sync.WaitGroup
var permutations int
var permutationsMutex sync.Mutex
func main() {
n := 9
wg.Add(n)
for i := 0; i < n; i++ {
var arr []int
for j := 0; j < n; j++ {
if i != j {
arr = append(arr, j+1)
}
}
go threadFunction(n-1, i+1, arr)
}
wg.Wait()
fmt.Println(permutations)
}
func threadFunction(k int, suffix int, arr []int) {
defer wg.Done()
heapPermutation(k, suffix, arr)
}
func heapPermutation(k int, prefix int, arr []int) {
if k == 1 {
arr = append(arr, prefix)
permutationsMutex.Lock()
permutations++
permutationsMutex.Unlock()
} else {
heapPermutation(k-1, prefix, arr)
for i := 0; i < k-1; i++ {
if k%2 == 0 {
arr[i], arr[k-1] = arr[k-1], arr[i]
} else {
arr[0], arr[k-1] = arr[k-1], arr[0]
}
heapPermutation(k-1, prefix, arr)
}
}
}