algorithm - 递归算法中的 Go channel 导致重复值

Question

起点

我有一个 Heap's algorithm 的实现在 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]

它打印出输入集的正确六个排列，所以一切正常。

问题

但现在我想将排列返回给调用者，而不是在函数中打印出来。

我尝试通过将 channel 传递给函数然后将每个排列发送到 channel 而不是打印它来做到这一点:

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 的值被发送到 channel ，而不是在指定的行中打印出来Permutation 函数体。

Answer 1

这样，您将 slice a 发送到主 goroutine:

  if k == 1 {
    c <- a
  }

当 main goroutine 正在努力打印它时，您开始修改 a。所以 slice 在您打印时正在修改。

您可以发送一份副本:

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