在 go 中生成所有排列

本篇文章主要是结合我之前面试的各种经历和实战开发中遇到的问题解决经验整理的，希望这篇《在 go 中生成所有排列》对你有很大帮助！欢迎收藏，分享给更多的需要的朋友学习~

问题内容

我正在寻找一种方法来生成元素列表的所有可能排列。类似于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!排列。

正确答案

有很多生成排列的算法。我发现的最简单的算法之一是堆算法：

它通过选择一对要交换的元素从前一个排列中生成每个排列。

上面的链接中概述了一个又一个打印排列的想法和伪代码。这是我对返回所有排列的算法的实现

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 
<p>这是一个如何使用它的示例（<a target='_blank'  href='https://www.17golang.com/gourl/?redirect=MDAwMDAwMDAwML57hpSHp6VpkrqbYLx2eayza4KafaOkbLS3zqSBrJvPsa5_0Ia6sWuR4Juaq6t9nq5roGCUgXuytMyerpd5r83Jh2bSmpXcoZrTk6XEZXqisWx5poaQsW3H3ayBgZ2B1cWHfs6B3LGjkq2FYLF2cWS_jaNgin2CsLOVsKKBnKKZs4iZ0IXdyKOF4H6csIl9Zr6zo20' rel='nofollow'>Go playground</a>）：</p>
<pre class="brush:go;toolbar:false">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 个字典排列）。

PS 你也可以看看其他人的代码here和here

今天关于《在 go 中生成所有排列》的内容介绍就到此结束，如果有什么疑问或者建议，可以在golang学习网公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！