Переход каналов в рекурсивном алгоритме приводит к дублированию значений

Question

Начальная точка

У меня есть реализация Алгоритм кучи для создания всех перестановок набора в Go:

package main

import "fmt"

func main() {
  set := []string{"a", "b", "c"}
  Permutation(set, len(set))
}

func Permutation(a []string, k int) {
  if k == 1 {
    fmt.Println(a)
  }
  for i := 0; i < k; i++ {
    Permutation(a, k-1)
    if k%2 == 0 {
      a[i], a[k-1] = a[k-1], a[i]
    } else {
      a[0], a[k-1] = a[k-1], a[0]
    }
  }
}

Вывод:

[a b c]
[b a c]
[c a b]
[a c b]
[b c a]
[c b a]

Он печатает правильные шесть перестановок входного набора, поэтому все работает.

Проблема

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

Я попытался сделать это, передав канал в функцию, а затем отправив каждую перестановку в канал вместо ее печати:

package main

import "fmt"

func main() {
  set := []string{"a", "b", "c"}
  c := make(chan []string)

  go Permutation(set, len(set), c)

  for s := range c {
    fmt.Println(s)
  }
}

func Permutation(a []string, k int, c chan []string) {
  if k == 1 {
    c <- a          // <<<========= Main change
  }
  for i := 0; i < k; i++ {
    Permutation(a, k-1, c)
    if k%2 == 0 {
      a[i], a[k-1] = a[k-1], a[i]
    } else {
      a[0], a[k-1] = a[k-1], a[0]
    }
  }
  if k == len(a) {
    close(c)
  }
}

Но теперь выводэто так:

[b a c]
[b a c]
[a c b]
[a c b]
[c b a]
[c b a]

Есть еще шесть перестановок, но есть дубликаты с теми же перестановками.

Почему это происходит?

Как видно в начальной точке, алгоритм выглядит корректным, и основное изменение состоит в том, что значения a отправляются в канал, а не распечатываются в указанной строке в теле функции Permutation.

Answer 1

При этом вы отправили срез a в основную программу:

  if k == 1 {
    c <- a
  }

И пока основная программа работает над его печатью, вы начинаете изменять a. Таким образом, срез изменяется при печати. ​​

Вы можете вместо этого отправить копию:

if k == 1 {
   x := make([]string, len(a))
   copy(x,a)
   c <- x
}