добавление к ломтикам рекурсивно

Question

Я пытаюсь реализовать простую функцию в Go, которая возвращает все перестановки набора чисел. Я получил это, чтобы напечатать все перестановки, но я не могу заставить это добавить их к 2D-срезу. это код для перестановок:

package main

import "fmt"

// Generating permutation using Heap Algorithm
func heapPermutation(p *[][]int, a []int, size, n, count int) int {
    count++
    // if size becomes 1 then prints the obtained
    // permutation
    if size == 1 {
        fmt.Println(a)
        *p = append(*p, a)
        return count
    }
    i := 0
    for i < size {
        count = heapPermutation(p, a, size-1, n, count)

        // if size is odd, swap first and last
        // element
        // else If size is even, swap ith and last element
        if size%2 != 0 {
            a[0], a[size-1] = a[size-1], a[0]
        } else {
            a[i], a[size-1] = a[size-1], a[i]
        }
        i++
    }
    return count
}

и это основная функция:

func main() {
    listNumbers := []int{1, 2, 3}
    n := len(listNumbers)
    permutations := make([][]int, 0)
    p := &permutations
    heapPermutation(p, listNumbers, n, n, 0)
    fmt.Print(permutations)
}

когда я запускаю этот код, я получаю этот вывод:

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

Итак, вы можете видеть, что функция способна находить перестановки, но когда я пытаюсь добавить ее, происходит нечто странное. Если я добавляю fmt.Println(*p) перед каждым добавлением, я получаю следующий результат:

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

Таким образом, каждый раз, когда я использую команду добавления, это выглядит так, как будто добавляется новый фрагмент и перезаписываются все остальные фрагменты. Почему это случилось? Кстати, то же самое, если я просто использую глобальную переменную вместо указателя.

Спасибо

Answer 1

Вы не добавляете разные []int фрагменты в больший [][]int фрагмент, вы добавляете один и тот же (a) снова и снова. И вы модифицируете a несколько раз. К концу вы изменили a до первоначального значения, поэтому ваш конечный результат выглядит как исходный ввод listNumbers, повторенный шесть раз.

Вот более простой способ увидеть задача:

package main

import "fmt"

func main() {
  a := []int{1}
  p := [][]int{a, a, a}
  fmt.Println(p) // [[1] [1] [1]]
  a[0] = 2
  fmt.Println(p) // [[2] [2] [2]]
}

Чтобы получить желаемый результат, вам нужно сделать копии a, которые не будут затронуты позже при последующем изменении a. Например:

tmp := make([]int, len(a))
copy(tmp, a)
*p = append(*p, tmp)

Подробнее о copy здесь .

Answer 2

Хорошо, с помощью @Amit Кумар Гупта, я получил его на работу! это новый код: пакет main

    import "fmt"

    // Generating permutation using Heap Algorithm
    func heapPermutation(p *[][]int, a []int, size, n, count int) int {
        count++
        // if size becomes 1 then prints the obtained
        // permutation
        if size == 1 {
            fmt.Println(a)
            tmp := make([]int, len(a)) 
            /*
            'a' is like a pointer to an object,
            every time you modify 'a' it will change all the elemets of 'a'
            in the permutations list.
            like so
            :
            a := []int{1}
            p := [][]int{a, a, a}
            fmt.Println(p) // [[1] [1] [1]]
            a[0] = 2
            fmt.Println(p) // [[2] [2] [2]]
            */
            copy(tmp, a)
            *p = append(*p, tmp)
            fmt.Println(*p)
            return count
        }
        i := 0
        for i < size {
            count = heapPermutation(p, a, size-1, n, count)

            // if size is odd, swap first and last
            // element
            // else If size is even, swap ith and last element
            if size%2 != 0 {
                a[0], a[size-1] = a[size-1], a[0]
            } else {
                a[i], a[size-1] = a[size-1], a[i]
            }
            i++
        }
        return count
    }

этот код дает ответ:

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