# Compute permutations (recursion)

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)
}
``````

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.

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)

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...)
}
``````
1 Like

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

1 Like

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.