我正在寻找一种生成给定元素列表的所有可能排列的方法。类似于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！个排列。
有很多算法可以生成排列。我发现其中最简单的一个是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 中看到的那样）。如果出于某种原因您需要对其进行排序，我发现一种方法是从阶乘数系统生成它们（在排列部分中有描述，并允许快速找到第n个字典序排列）。
以下是一个可以遍历所有排列而不必提前生成它们的代码。切片 p 将中间状态保存为 Fisher-Yates 洗牌算法中的偏移量。这具有很好的特性，即 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))
}
}
var res [][]int
func permute(nums []int) [][]int {
res=make([][]int,0)
n:=len(nums)
var backTrack func(int)
backTrack=func(first int){
if first == n{
temp:=make([]int, n)
copy(temp,nums)
res = append(res, temp)
}
for i:=first;i<n;i++{
nums[first],nums[i] = nums[i],nums[first]
backTrack(first+1)
nums[first],nums[i] = nums[i],nums[first]
}
}
backTrack(0)
return res
}
这里是另一种变化：
// heap algorithm
func permutations(arr []int, l int, p [][]int) [][]int {
if l == 1 { p = append(p, append([]int{}, arr...)) }
for i := 0 ; i < l ; i++ {
p = permutations(arr, l-1, p)
if l % 2 == 1 {
arr[0], arr[l-1] = arr[l-1], arr[0]
} else {
arr[i], arr[l-1] = arr[l-1], arr[i]
}
}
return p
}
func generateIntPermutations(array []int, n int, result *[][]int) {
if n == 1 {
dst := make([]int, len(array))
copy(dst, array[:])
*result = append(*result, dst)
} 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 -> [[0 1 2] [1 0 2] [2 1 0] [1 2 0] [2 0 1] [0 2 1]]
另一个可用的代码
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]]
使用简单算法的golang排列代码
package main
import "fmt"
func permute(arr[] int, start int, end int) {
if start == end {
fmt.Println(arr)
return
}
for i:=start;i<end;i++ {
arr[i],arr[start] = arr[start],arr[i]
permute(arr,start+1,end)
arr[i],arr[start] = arr[start],arr[i]
}
}
func main() {
arr := []int{1,2,3}
end := len(arr)
start := 0
permute(arr,start,end)
}
permutations := iterium.Permutations([]string{"A", "B", "C", "D"}, 2)
toSlice, _ := permutations.Slice()
fmt.Println("Total:", permutations.Count())
fmt.Println(toSlice)
结果：
Total: 12
[
[A, B] [A, C] [A, D] [B, A] [B, C] [B, D]
[C, B] [C, A] [C, D] [D, B] [D, C] [D, A]
]