Compute permutations (recursion)

[reeed.GRD (Orion McFlurry)]

https://play.golang.org/p/cS7S3tYAXrn

The recursive function permute() works when passed a slice of 6 unique ints, but fails when passed 7 or more ints.

Where am I going wrong?

Code duplicated here:

package main

import (
	"fmt"
	"strconv"
	"strings"
)

// recursive function that returns all possible permutations of the given input ([]int)
func permute(prefix []int, input []int) [][]int {
	if len(input) == 0 {
		return [][]int{prefix}
	}
	// fmt.Println("permute", prefix, input)
	var res [][]int
	for i := range input {
		// cc := copy(input)
		cc := make([]int, len(input))
		copy(cc, input) // builtin
		if i > 0 {
			cc[0], cc[i] = cc[i], cc[0]
		}
		newprefix := append(prefix, cc[0])
		p := permute(newprefix, cc[1:])
		res = append(res, p...)
		// fmt.Println("  append", prefix, p)
	}
	// fmt.Println("  res", prefix, res)
	return res
}

// use a map to count the no of occurrences of each permutation
// input: [] of permutations ([]int)
func checkdup(input [][]int) {
	m := make(map[string]int)
	for _, n := range input {
		var s []string
		for _, i := range n {
			s = append(s, strconv.Itoa(i))
		}
		key := strings.Join(s, "-")
		m[key]++
	}
	fmt.Printf("%d in the map, %d unique\n", len(input), len(m))
}

// returns the factorial of n
func factorial(n int) int {
	i := n
	for i > 1 {
		i--
		n = n * i
	}
	return n
}

func main() {
	a := []int{1, 2, 3, 4, 5, 6, 7}
	fmt.Println("permute 6 (6! is", factorial(6), ")")
	p = permute(nil, a[:6])
	checkdup(p)
	fmt.Println("permute 7 (7! is", factorial(7), ")")
	p = permute(nil, a[:7])
	checkdup(p)
}

[reeed.GRD (Orion McFlurry)]

I should add that when given 7 ints, I expect 5040 unique permutations, but I’m getting half of this number; each returned permutation is duplicated.

[christophberger]

Fun fact:

For 7 ints, tbe observed number of permutations is half of the expected one.
For 8 ints, the observed number is a sixth of the expected one.
For 9 ints and 10 ints, the results are correct again.

permute 6 (6! is 720)
720 in the map, 720 unique
permute 7 (7! is 5040)
5040 in the map, 2520 unique
permute 8 (8! is 40320)
40320 in the map, 6720 unique
permute 9 (9! is 362880)
362880 in the map, 362880 unique
permute 10 (10! is 3628800)
3628800 in the map, 3628800 unique

(Maybe this is helpful for troubleshooting but I am too tired to dig deeper)

[christophberger]

The problem is

newprefix = append(prefix, cc[0])

This code works:

newprefix := make([]int, len(prefix)+1)
copy(newprefix, prefix)
newprefix = append(newprefix, cc[0])

As a rule of thumb, append should only be used for appending a value to a given slice, and not for creating a new one in the same step.

The cause of the glitch is how append affects the underlying array. append may modify the array in-place or, if the capacity is not sufficient, create a new array, copy the old one over, and start appending there.

See the basic flow of in-place vs append here (in the append() section).

This flow can lead to unexpected behavior when the receiver of append's return value is not the same slice that is passed to append.

This StackOverflow answer suggests a function that combines copy and append:

func copyAndAppend(i []int, vals ...int) []int {
    j := make([]int, len(i), len(i)+len(vals))
    copy(j, i)
    return append(j, vals...)
}

[reeed.GRD (Orion McFlurry)]

wow thank you! The explanation and links are much appreciated!