将指针传递给go中的切片时发生意外行为

Question

The following go program is supposed to generate all permutations of a slice of integers:

package main
import "fmt"

func permute(nums []int) [][]int {
    var res [][]int
    var s []int
    permuteHlp(&res, nums, 0, s)
    return res
}

func permuteHlp(res *[][]int, nums []int, i int, s []int) {
    if i == len(nums) {
        *res = append(*res, s)
        return
    }

    for j := i; j < len(nums); j++ {
        s = append(s, nums[j])
        nums[i], nums[j] = nums[j], nums[i]
        permuteHlp(res, nums, i+1, s)
        s = s[:len(s)-1]
        nums[i], nums[j] = nums[j], nums[i]
    }
}

func main() {
    x := []int{1,2,3,4}
    y := permute(x)

    fmt.Println(y)
}

The output is unexpected

[[1 2 4 3] [1 2 4 3] [1 3 4 2] [1 3 4 2] [1 4 2 3] [1 4 2 3] [2 1 4 3] [2 1 4 3] [2 3 4 1] [2 3 4 1] [2 4 1 3] [2 4 1 3] [3 2 4 1] [3 2 4 1] [3 1 4 2] [3 1 4 2] [3 4 2 1] [3 4 2 1] [4 2 1 3] [4 2 1 3] [4 3 1 2] [4 3 1 2] [4 1 2 3] [4 1 2 3]]

I don't understand what is wrong here. I would appreciate any help. Thank you!

Answer 1

There's no need for a pointer to the slice since slices are pointers themselves. "a slice is a reference to a contiguous segment of an array.", reference.

The strange behavior you're seeing is because you're using append, when a slice grows beyond its capacity it's required to create a new slice with increased capacity and copy all the contents of the original one (this is what append does behind the scenes), hence new slice is no longer pointing to the original underlying array.

Instead of modifying the incoming parameter, I suggest returning the slice as a return value for the function.

func permute(nums []int) [][]int {
   res := permuteHlp(nums, 0, new([]int))
   return res
}

I recommend you read the blog post in golang.org about slices internals, here

---

Edit:

I add a refactor, taking the algorithm from this answer.

package main

import (
    "fmt"  
)

func permutations(arr []int)[][]int{
    var helper func([]int, int)
    res := [][]int{}

    helper = func(arr []int, n int){
        if n == 1{
            tmp := make([]int, len(arr))
            copy(tmp, arr)
            res = append(res, tmp)
        } else {
            for i := 0; i < n; i++{
                helper(arr, n - 1)
                if n % 2 == 1{
                    tmp := arr[i]
                    arr[i] = arr[n - 1]
                    arr[n - 1] = tmp
                } else {
                    tmp := arr[0]
                    arr[0] = arr[n - 1]
                    arr[n - 1] = tmp
                }
            }
        }
    }
    helper(arr, len(arr))
    return res
}

func main() {
    x := []int{1,2,3,4}
    d := permutations(x)
    fmt.Print(d)
}

Generally you won't want to have a pointer to a slice, instead, return a new one from the function, another thing to comment on, try not to use recursion if possible as golang doesn't have tail call optimization, and its loops perform amazingly. Hope it helps!