在go中生成所有排列

本文介绍了在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 ，您也可以在此处和此处