4
\$\begingroup\$

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...

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – mh-cbon Sep 15 at 12:24
  • \$\begingroup\$ 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. \$\endgroup\$ – mh-cbon Sep 15 at 12:30
1
\$\begingroup\$

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
 }

\$\endgroup\$
  • \$\begingroup\$ 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! \$\endgroup\$ – zack Sep 12 at 4:10
  • \$\begingroup\$ 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. \$\endgroup\$ – ferada Sep 12 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.