Неожиданное поведение при передаче указателя на фрагмент в go

Question

Следующая программа go должна генерировать все перестановки среза целых чисел:

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

Вывод неожиданный

[[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]]

Я не понимаю, что здесь не так,Буду признателен за любую помощь.Спасибо!

Answer 1

Нет необходимости в указателе на срез, так как срезы сами являются указателями.«срез - это ссылка на непрерывный сегмент массива.», reference .

Странное поведение, которое вы видите, это то, что вы используете append, когда срез выходит за пределыего емкость требуется для создания нового среза с увеличенной емкостью и копирования всего содержимого оригинального (это то, что приложение добавляет за кулисами), следовательно, новый срез больше не указывает на исходный базовый массив.

Вместо того, чтобы изменять входящий параметр, я предлагаю вернуть срез в качестве возвращаемого значения для функции.

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

Рекомендую прочитать сообщение в блоге на golang.org о внутренних фрагментах, здесь

---

Редактировать:

Я добавляю рефакторинг, взяв алгоритм из этот ответ .

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

Обычно вы выиграли 'Если вы не хотите иметь указатель на фрагмент, вместо этого возвращайте новый из функции, еще одну вещь для комментирования, старайтесь не использовать рекурсию, если это возможно, поскольку golang не имеет оптимизации хвостового вызова,д его петли работают удивительно.Надеюсь, это поможет!

Answer 2

Вы передаете указатель на тот же фрагмент.В конце концов вы получите несколько указателей на один и тот же фрагмент в ваших результатах, поэтому, конечно, все значения будут идентичны - это один и тот же фрагмент, напечатанный снова и снова.

Стоит также отметить, чтоуказатель на срез - это редко то, что вам нужно, поскольку срезы уже содержат указатель на базовый массив.