在go中生成所有排列 [英] Generate all permutations in go
问题描述
我正在寻找一种生成元素列表的所有可能排列的方法。类似于 Python的 itertools.permutations (arr)
I am looking for a way to generate all possible permutations of a list of elements. Something similar to 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!
排列。
With the difference that I do not care whether permutations would be generated on demand (like a generator in python) or all together. I also do not care whether they will be lexicographically sorted. All I need is to somehow get these n!
permutations.
推荐答案
有许多算法可以生成置换。我发现的最容易的方法之一是堆的算法:
There are a lot of the algorithms that generate permutations. One of the easiest I found is Heap's algorithm:
它通过选择一对要交换的元素
来生成前一个排列的每个排列。
It generates each permutation from the previous one by choosing a pair of elements to interchange.
上面的链接概述了一个想法和一个伪代码,该伪代码一个接一个地打印排列。这是我返回所有排列的算法的实现
The idea and a pseudocode that prints the permutations one after another is outlined in the above link. Here is my implementation of the algorithm which returns all permutations
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
}
这是使用方法的示例(去操场):
and here is an example of how to use it (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个字典编排)。
One thing to notice that the permutations are not sorted lexicographically (as you have seen in itertools.permutations
). If for some reason you need it to be sorted, one way I have found it is to generate them from a factorial number system (it is described in permutation section
and allows to quickly find n-th lexicographical permutation).
PS ,您也可以在此处和< a href = http://rosettacode.org/wiki/Permutations#Go rel = noreferrer>此处
这篇关于在go中生成所有排列的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!