在 go 中生成所有排列

Question

我正在寻找一种方法来生成元素列表的所有可能排列。类似于python的东西 itertools.permutations(arr)

permutations ([])

[]

permutations ([1])

[1]

permutations ([1,2])

[1, 2]

[2, 1]

permutations ([1,2,3])

[1, 2, 3]

[1, 3, 2]

[2, 1, 3]

[2, 3, 1]

[3, 1, 2]

[3, 2, 1]

不同之处在于我不关心排列是按需生成（如 python 中的生成器）还是一起生成。我也不关心它们是否会按字典顺序排序。我所需要的只是以某种方式获得这些n!排列。

Answer 1

有很多生成排列的算法。我发现的最简单的算法之一是Heap 算法：它通过选择一对要交换的元素从前一个排列中生成每个排列。上面的链接概述了这个想法和一个接一个打印排列的伪代码。这是我对返回所有排列的算法的实现func permutations(arr []int)[][]int{&nbsp; &nbsp; var helper func([]int, int)&nbsp; &nbsp; res := [][]int{}&nbsp; &nbsp; helper = func(arr []int, n int){&nbsp; &nbsp; &nbsp; &nbsp; if n == 1{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; tmp := make([]int, len(arr))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; copy(tmp, arr)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; res = append(res, tmp)&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for i := 0; i < n; i++{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; helper(arr, n - 1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if n % 2 == 1{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; tmp := arr[i]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr[i] = arr[n - 1]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr[n - 1] = tmp&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; tmp := arr[0]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr[0] = arr[n - 1]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr[n - 1] = tmp&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; helper(arr, len(arr))&nbsp; &nbsp; return res}这是如何使用它的示例（Go playground）：arr := []int{1, 2, 3}fmt.Println(permutations(arr))[[1 2 3] [2 1 3] [3 2 1] [2 3 1] [3 1 2] [1 3 2]]要注意的一件事是排列没有按字典顺序排序（如您在 中看到的itertools.permutations）。如果由于某种原因您需要对它进行排序，我发现它的一种方法是从阶乘数系统中生成它们（它在中描述permutation section并允许快速找到第 n 个词典排列）。

Answer 2

这是迭代所有排列而不首先生成它们的代码。切片p将中间状态保持为 Fisher-Yates shuffle 算法中的偏移量。这有一个很好的特性，即零值p描述了身份排列。package mainimport "fmt"func nextPerm(p []int) {&nbsp; &nbsp; for i := len(p) - 1; i >= 0; i-- {&nbsp; &nbsp; &nbsp; &nbsp; if i == 0 || p[i] < len(p)-i-1 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; p[i]++&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; p[i] = 0&nbsp; &nbsp; }}func getPerm(orig, p []int) []int {&nbsp; &nbsp; result := append([]int{}, orig...)&nbsp; &nbsp; for i, v := range p {&nbsp; &nbsp; &nbsp; &nbsp; result[i], result[i+v] = result[i+v], result[i]&nbsp; &nbsp; }&nbsp; &nbsp; return result}func main() {&nbsp; &nbsp; orig := []int{11, 22, 33}&nbsp; &nbsp; for p := make([]int, len(orig)); p[0] < len(p); nextPerm(p) {&nbsp; &nbsp; &nbsp; &nbsp; fmt.Println(getPerm(orig, p))&nbsp; &nbsp; }}

Answer 3

另一个工作代码package permutationsimport "fmt"func AllPermutation(a []int) {&nbsp; &nbsp; var res [][]int&nbsp; &nbsp; calPermutation(a, &res, 0)&nbsp; &nbsp; fmt.Println(res)}func calPermutation(arr []int, res *[][]int, k int) {&nbsp; &nbsp; for i := k; i < len(arr); i++ {&nbsp; &nbsp; &nbsp; &nbsp; swap(arr, i, k)&nbsp; &nbsp; &nbsp; &nbsp; calPermutation(arr, res, k+1)&nbsp; &nbsp; &nbsp; &nbsp; swap(arr, k, i)&nbsp; &nbsp; }&nbsp; &nbsp; if k == len(arr)-1 {&nbsp; &nbsp; &nbsp; &nbsp; r := make([]int, len(arr))&nbsp; &nbsp; &nbsp; &nbsp; copy(r, arr)&nbsp; &nbsp; &nbsp; &nbsp; *res = append(*res, r)&nbsp; &nbsp; &nbsp; &nbsp; return&nbsp; &nbsp; }}func swap(arr []int, i, k int) {&nbsp; &nbsp; arr[i], arr[k] = arr[k], arr[i]}//result [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 2 1] [3 1 2]]