在go中生成所有排列

Question

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

有很多算法可以生成permutations。我找到的最简单的一个是Heap's algorithm：

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

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

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中看到的那样）。如果由于某种原因你需要对它进行排序，我发现它的一种方法是从factorial number system生成它们（它在permutation section中描述并允许快速找到第n个词典排列）。

附：你也可以看看其他人代码here和here

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

不要使用递归！如果你想利用go的并发性和可扩展性尝试像QuickPerm这样的东西

package main

import (
    "fmt"
)

func main() {
    for perm := range GeneratePermutations([]int{1,2,3,4,5,6,7}){
        fmt.Println(perm)
    }
}
func GeneratePermutations(data []int) <-chan []int {  
    c := make(chan []int)
    go func(c chan []int) {
        defer close(c) 
        permutate(c, data)
    }(c)
    return c 
}
func permutate(c chan []int, inputs []int){
    output := make([]int, len(inputs))
    copy(output, inputs)
    c <- output

    size := len(inputs)
    p := make([]int, size + 1)
    for i := 0; i < size + 1; i++ {
        p[i] = i;
    }
    for i := 1; i < size;{
        p[i]--
        j := 0
        if i % 2 == 1 {
            j = p[i]
        }
        tmp := inputs[j]
        inputs[j] = inputs[i]
        inputs[i] = tmp
        output := make([]int, len(inputs))
        copy(output, inputs)
        c <- output
        for i = 1; p[i] == 0; i++{
            p[i] = i
        }
    }
}

Answer 4

在我的情况下，我有一个数组的引用，然后我在你的例子中做了一些更改：

func generateIntPermutations(array []int, n int, result *[][]int) {
    if n == 1 {
        *result = append(*result, array)
    } else {
        for i := 0; i < n; i++ {
            generateIntPermutations(array, n-1, result)
            if n%2 == 0 {
                // Golang allow us to do multiple assignments
                array[0], array[n-1] = array[n-1], array[0]
            } else {
                array[i], array[n-1] = array[n-1], array[i]
            }
        }
    }
}
numbers := []int{0, 1, 2}
var result [][]int
generateIntPermutations(numbers, len(numbers), &result)

// result -> [[2 0 1] [2 0 1] [2 0 1] [2 0 1] [2 0 1] [2 0 1]]