Go语言创建排列组合

huangapple
go评论125阅读模式
英文:

Go language create permutations

问题

今天我尝试用Go语言迈出第一步。我试图编写一个函数，用于生成给定列表的所有排列组合。起初我完全失败了，所以我尝试先用Python编写这个函数，然后逐步将其翻译成Go语言：

Python版本：

  1. def get_permutations(elements):
  2.     permutations = []
  3.     if len(elements) == 1:
  4.         return [elements]
  5.     for i in range(len(elements)):
  6.         for perm in get_permutations(elements[0:i] + elements[i+1:]):
  7.             permutations.append([elements[i]] + perm)
  8.     return permutations
  10. print(get_permutations([1,2,3]))

Go版本：

  1. func getPermutations(elements []int) [][]int {
  2.     permutations := [][]int{}
  3.     if len(elements) == 1 {
  4.         permutations = [][]int{elements}
  5.         return permutations
  6.     }
  7.     for i := range elements {
  8.         for _, perm := range getPermutations(append(elements[0:i], elements[i+1:]...)) {
  9.             permutations = append(permutations, append([]int{elements[i]}, perm...))
  10.         }
  11.     }
  12.     return permutations
  13. }
  15. func main() {
  16.     x := getPermutations([]int{1, 2, 3})
  17.     fmt.Print(x)
  18. }

Python版本输出结果为：

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

而Go版本输出结果为：

[[3 3 3] [3 3 3] [3 3 3] [3 3 3] [3 3 3] [3 3 3]]

我真的希望有人能帮助我。我真的想知道，在Go代码中我做错了什么。

英文:

Today I tried to do my first steps with go.
I tried to write a function, which creates all permutations of a given list.
First I failed completely, so I tried to write the function with python and translate it step by step to go:

python:

  1. def get_permutations(elements):
  2.     permutations = []
  3.     if len(elements) == 1:
  4.         return [elements]
  5.     for i in range(len(elements)):
  6.         for perm in get_permutations(elements[0:i] +  elements[i+1:]):
  7.             permutations.append([elements[i]] + perm)
  8.     return permutations
  10. print(get_permutations([1,2,3]))

go:

  1. func getPermutations(elements []int) [][]int {
  2. 	permutations := [][]int{}
  3. 	if len(elements) == 1 {
  4. 		permutations = [][]int{elements}
  5. 		return permutations
  6. 	}
  7. 	for i := range elements {
  8. 		for _, perm := range getPermutations(append(elements[0:i], elements[i+1:]...)) {
  9. 			permutations = append(permutations, append([]int{elements[i]}, perm...))
  10. 		}
  11. 	}
  12. 	return permutations
  13. }
  15. func main() {
  16. 	x := getPermutations([]int{1, 2, 3})
  17. 	fmt.Print(x)
  18. }

While the python version creates this ouput:

> [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

The go version creates this one:

> [[3 3 3] [3 3 3] [3 3 3] [3 3 3] [3 3 3] [3 3 3]]

I really someone can help me. I really would like to know, what I've done wrong in the go code

答案1

得分: 4

getPermutations函数在每次迭代中都会改变原始的elements切片。在修改之前，你需要先复制该切片。

  1. func getPermutations(elements []int) [][]int {
  2.     permutations := [][]int{}
  3.     if len(elements) == 1 {
  4.         permutations = [][]int{elements}
  5.         return permutations
  6.     }
  7.     for i := range elements {
  8.         el := make([]int, len(elements))
  9.         copy(el, elements)
  11.         // 或者通过append进行复制
  12.         // el := append([]int(nil), elements...)
  14.         for _, perm := range getPermutations(append(el[0:i], el[i+1:]...)) {
  15.             permutations = append(permutations, append([]int{elements[i]}, perm...))
  16.         }
  17.     }
  18.     return permutations
  19. }

链接：https://play.golang.org/p/oewV8iPd8E

英文:

The getPermutations function is mutating the original elements slice each iteration. You need to make a copy of that slice before you modify it.

  1. func getPermutations(elements []int) [][]int {
  2. 	permutations := [][]int{}
  3. 	if len(elements) == 1 {
  4. 		permutations = [][]int{elements}
  5. 		return permutations
  6. 	}
  7. 	for i := range elements {
  8. 		el := make([]int, len(elements))
  9. 		copy(el, elements)
  11. 		// or copy via append
  12. 		// el := append([]int(nil), elements...)
  14. 		for _, perm := range getPermutations(append(el[0:i], el[i+1:]...)) {
  15. 			permutations = append(permutations, append([]int{elements[i]}, perm...))
  16. 		}
  17. 	}
  18. 	return permutations
  19. }

https://play.golang.org/p/oewV8iPd8E

huangapple
  • 本文由 发表于 2017年2月3日 23:54:12
  • 转载请务必保留本文链接：https://go.coder-hub.com/42028130.html
  • go
  • python
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定