在 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{

    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 < n; i++{

                helper(arr, n - 1)

                if n % 2 == 1{

                    tmp := arr[i]

                    arr[i] = arr[n - 1]

                    arr[n - 1] = tmp

                } else {

                    tmp := arr[0]

                    arr[0] = arr[n - 1]

                    arr[n - 1] = tmp

                }

            }

        }

    }

    helper(arr, len(arr))

    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 main

import "fmt"

func nextPerm(p []int) {

    for i := len(p) - 1; i >= 0; i-- {

        if i == 0 || p[i] < len(p)-i-1 {

            p[i]++

            return

        }

        p[i] = 0

    }

}

func getPerm(orig, p []int) []int {

    result := append([]int{}, orig...)

    for i, v := range p {

        result[i], result[i+v] = result[i+v], result[i]

    }

    return result

}

func main() {

    orig := []int{11, 22, 33}

    for p := make([]int, len(orig)); p[0] < len(p); nextPerm(p) {

        fmt.Println(getPerm(orig, p))

    }

}

Answer 3

另一个工作代码

package permutations

import "fmt"

func AllPermutation(a []int) {

    var res [][]int

    calPermutation(a, &res, 0)

    fmt.Println(res)

}

func calPermutation(arr []int, res *[][]int, k int) {

    for i := k; i < len(arr); i++ {

        swap(arr, i, k)

        calPermutation(arr, res, k+1)

        swap(arr, k, i)

    }

    if k == len(arr)-1 {

        r := make([]int, len(arr))

        copy(r, arr)

        *res = append(*res, r)

        return

    }

}

func swap(arr []int, i, k int) {

    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]]