我正在尋找一種方法來生成元素列表的所有可能排列。類似于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]不同之處在于我不關(guān)心排列是按需生成（如 python 中的生成器）還是一起生成。我也不關(guān)心它們是否會按字典順序排序。我所需要的只是以某種方式獲得這些n!排列。
3 回答
拉丁的傳說
TA貢獻1789條經(jīng)驗 獲得超8個贊
有很多生成排列的算法。我發(fā)現(xiàn)的最簡單的算法之一是Heap 算法：
它通過選擇一對要交換的元素從前一個排列中生成每個排列。
上面的鏈接概述了這個想法和一個接一個打印排列的偽代碼。這是我對返回所有排列的算法的實現(xiàn)
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）。如果由于某種原因您需要對它進行排序，我發(fā)現(xiàn)它的一種方法是從階乘數(shù)系統(tǒng)中生成它們（它在中描述permutation section并允許快速找到第 n 個詞典排列）。
藍山帝景
TA貢獻1843條經(jīng)驗 獲得超7個贊
這是迭代所有排列而不首先生成它們的代碼。切片p將中間狀態(tài)保持為 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))
}
}
慕沐林林
TA貢獻2016條經(jīng)驗 獲得超9個贊
另一個工作代碼
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]]
- 3 回答
- 0 關(guān)注
- 245 瀏覽
添加回答
舉報
0/150
提交
取消