# Go function to generate permutations of a given integer array

I'm writing a function to generate a permutation of given []int:

// Input: [1,2,3]
// Output:
// [
//   [1,2,3],
//   [1,3,2],
//   [2,1,3],
//   [2,3,1],
//   [3,1,2],
//   [3,2,1]
// ]

func permute(nums []int) [][]int {
var tmp []int
var res [][]int
invalid_pos := make([]bool, len(nums))
res = backtrack(nums, tmp, invalid_pos, res)
return res
}

// backtrack generates all the permutations of the given nums and put them into res.
// invalid_pos keeps track of which number is valid to pick from nums to form a permutation
// tmp
func backtrack(nums []int, tmp []int, invalid_pos []bool, res [][]int) [][]int {
if len(tmp) == len(nums) {
tmp2 := make([]int, len(tmp))
copy(tmp2, tmp)
res = append(res, tmp2)
} else {
for i, num := range nums {
if invalid_pos[i] {
continue
}
invalid_pos[i] = true
tmp = append(tmp, num)
res = backtrack(nums, tmp, invalid_pos, res)
invalid_pos[i] = false
tmp = tmp[:len(tmp)-1]
}
}
return res
}


My question is do I need to make a copy copy(tmp2, tmp)? I read about capturing iteration variables and I was wondering if this will have any side effect? I think I can simplify the code by removing copy...

• from a codereview perspective, recursive function call should be avoided in go as TCO is not provided by the compiler (medium.com/@felipedutratine/…). As a consequence you better implement it using non recursive version of the algorithm. – mh-cbon Sep 15 '19 at 12:24
• also it is possible to write this using a more generic []interface{} input and [][]interface{} output. avoiding many copy-paste if you want to permute something that is not an int. – mh-cbon Sep 15 '19 at 12:30

To make it nicer for your reviewers you could post as a complete and runnable example:

package main

import "fmt"

...

func main() {
input := []int{1, 2, 3}
output := permute(input)
fmt.Printf("Input: %v\nOutput:\n", input)
for _, x := range output {
fmt.Printf("  %v\n", x)
}
}


With that out of the way, I'd simplify permute a bit:

func permute(nums []int) [][]int {
return backtrack(nums, []int{}, make([]bool, len(nums)), [][]int{})
}


In backtrack I'd consider returning early for the first case, that lets you remove one level of indentation for the rest:

func backtrack(nums []int, tmp []int, invalid_pos []bool, res [][]int) [][]int {
if len(tmp) == len(nums) {
tmp2 := make([]int, len(tmp))
copy(tmp2, tmp)
return append(res, tmp2)
}
...
}


Regarding your question: Well, what happens if you remove the copy call?

0 go % go run perm.go
Input: [1 2 3]
Output:
[0 0 0]
[0 0 0]
[0 0 0]
[0 0 0]
[0 0 0]
[0 0 0]


Clearly it does something and you cannot remove it just like that. It also has nothing to do with capturing iteration variables, the only ones you have here are i and num - both aren't even part of the copy call, plus, you're not capturing anything, there's no func() {...} declaration anywhere that even could capture variables.

Variable capturing and the (most common?) problem with it comes only if you have a construction like this:

for i := ... {
x := func() {
foo(i)
}
}


The i in the anonymous function is the one from the loop - and since it's always the same variable, all the created functions reference ... the same variable! That can be confusing since people might expect that on each iteration of the loop we're capturing that one value that i currently has. Go could've done that, but I'm guessing mostly for performance reasons that's not being done and you've to explicitly make it happen yourself:

for i := ... {
j := i
x := func() {
foo(j)
}
}


Now foo gets called with all the different values of i.

Okay so that's that, now I'd just recommend simplifying this algorithm to get rid of invalid_pos, tmp and the res parameter and do it all functionally and recursively. I'm saying that because the code right now is pretty complex for the problem and yet it doesn't do everything upfront that it could, like preallocating the res array to the final length, so it seems this is more of a learning exercise.

Start with the base cases, empty list and one element, then consider the one element longer list:

func permute2(nums []int) [][]int {
if len(nums) <= 1 {
return [][]int{nums}
}
result := [][]int{}
for i, x := range nums {
...
}
return result
}


Don't optimise to early for reusing things, that can also follow once the algorithm is in its most simple form; clarity comes first.

Hint: You can do it without copy or manually instantiating any more slices via []int{}, just check out append and how to do subslices. Take particular care to not simply append slices together without considering how the underlying data is going to be shared (that's why append([]int{}, <slice here>) might be necessary to prevent the slice from being modified).

As a spoiler:

func permute2(nums []int) [][]int {
if len(nums) <= 1 {
return [][]int{nums}
}
result := [][]int{}
for i, x := range nums {
without := append(append([]int{}, nums[:i]...), nums[i+1:]...)
for _, y := range permute2(without) {
result = append(result, append([]int{x}, y...))
}
}
return result
}

• Thanks for your detailed answer. I run your main locally; remove tmp2 := make([]int, len(tmp)) and copy(tmp2, tmp); and I still get the correct result. I'm running on a Mac. I'm not sure what happened. Also, I was wondering where I need to use "subslice" in the ...? Can you please illustrate a little bit more? Thanks! – zack Sep 12 '19 at 4:10
• I'm not sure what happened, I'm very sure though that the copy copies over the values, so I don't see how removing it can keep the behaviour the same ... Okay, I'll amend the example. – ferada Sep 12 '19 at 9:39

Personally, I would remove the invalid_pos slice. Alternatively, you can call your recursive function using a copy of the original slice with the used element removed. The following function can remove that element and return a copy:

func cutSlice(nums []int, i int) []int {
res := append(append([]int{}, nums[:i]...), nums[i+1:]...)
return res
}


Additionally, your function does not need to return anything. You can change the header of the slice res (which keeps some metadata and a pointer to the slice). To change that header you need to pass a pointer to your function.

func permute(nums []int) [][]int {
var res [][]int
permuteHelper(nums, []int{}, &res)
return res
}


This way the code is simplified, and you can have a more concise and readable code.

func permuteHelper(nums []int, list []int, res *[][]int) {
if len(nums) == 0 {
*res = append(*res, list)
return
}
for j, el := range nums {
tmp := append(append([]int{}, list...), el)
permuteHelper(cutSlice(nums, j), tmp, res)
}
}


Regarding the copy function in that case, it is not needed. A copy of the list under construction is passed in the recursive call in the first place.