在Go中实现Ruby风格的笛卡尔积。

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

Implement Ruby style Cartesian product in Go

问题

我想要获取a、b、c、d的笛卡尔积：

  1. a = ['a1']
  2. b = ['b1', 'b2']
  3. c = ['c1', 'c2', 'c3']
  4. d = ['d1']

以下是Ruby代码：

  1. e = [b, c, d]
  2. print a.product(*e)

输出结果为：

  1. [
  2.   ["a1", "b1", "c1", "d1"],
  3.   ["a1", "b1", "c2", "d1"],
  4.   ["a1", "b1", "c3", "d1"],
  5.   ["a1", "b2", "c1", "d1"],
  6.   ["a1", "b2", "c2", "d1"],
  7.   ["a1", "b2", "c3", "d1"]
  8. ]

在Golang中是否有类似的包或函数可以实现笛卡尔积？这只是一个简化版本，实际上输入数据可能是这样的：[['a1'], ['b1','b2'], ['c1','c2','c3'],['d1'],['e1',...],...]。

英文:

I want to get the Cartesian product of a, b, c, d:

  1. a = ['a1']
  2. b = ['b1', 'b2']
  3. c = ['c1', 'c2', 'c3']
  4. d = ['d1']

Here is code in Ruby:

  1. e = [b, c, d]
  2. print a.product(*e)

Output is:

  1. [
  2.   ["a1", "b1", "c1", "d1"],
  3.   ["a1", "b1", "c2", "d1"],
  4.   ["a1", "b1", "c3", "d1"],
  5.   ["a1", "b2", "c1", "d1"],
  6.   ["a1", "b2", "c2", "d1"],
  7.   ["a1", "b2", "c3", "d1"]
  8. ]

Is there a similar package or function that could do product in Golang?
This is just simplified version, in fact, the input data is like [['a1'], ['b1','b2'], ['c1','c2','c3],['d1'],['e1',...],...].

答案1

得分: 8

如果您需要在编译时未知的嵌套索引循环集，可以使用以下代码：

  1. package main
  3. import "fmt"
  5. // NextIndex将ix设置为字典顺序的下一个值，
  6. // 对于每个i>0，0 <= ix[i] < lens(i)。
  7. func NextIndex(ix []int, lens func(i int) int) {
  8.     for j := len(ix) - 1; j >= 0; j-- {
  9.         ix[j]++
  10.         if j == 0 || ix[j] < lens(j) {
  11.             return
  12.         }
  13.         ix[j] = 0
  14.     }
  15. }
  17. func main() {
  18.     e := [][]string{
  19.         {"a1"},
  20.         {"b1", "b2"},
  21.         {"c1", "c2", "c3"},
  22.         {"d1"},
  23.     }
  24.     lens := func(i int) int { return len(e[i]) }
  26.     for ix := make([]int, len(e)); ix[0] < lens(0); NextIndex(ix, lens) {
  27.         var r []string
  28.         for j, k := range ix {
  29.             r = append(r, e[j][k])
  30.         }
  31.         fmt.Println(r)
  32.     }
  33. }

输出结果为：

  1. [a1 b1 c1 d1]
  2. [a1 b1 c2 d1]
  3. [a1 b1 c3 d1]
  4. [a1 b2 c1 d1]
  5. [a1 b2 c2 d1]
  6. [a1 b2 c3 d1]
英文:

If you need an unknown-at-compile-time set of nested index loops, you can use code like this.

  1. package main
  3. import &quot;fmt&quot;
  5. // NextIndex sets ix to the lexicographically next value,
  6. // such that for each i&gt;0, 0 &lt;= ix[i] &lt; lens(i).
  7. func NextIndex(ix []int, lens func(i int) int) {
  8. 	for j := len(ix) - 1; j &gt;= 0; j-- {
  9. 		ix[j]++
  10. 		if j == 0 || ix[j] &lt; lens(j) {
  11. 			return
  12. 		}
  13. 		ix[j] = 0
  14. 	}
  15. }
  17. func main() {
  18. 	e := [][]string{
  19. 		{&quot;a1&quot;},
  20. 		{&quot;b1&quot;, &quot;b2&quot;},
  21. 		{&quot;c1&quot;, &quot;c2&quot;, &quot;c3&quot;},
  22. 		{&quot;d1&quot;},
  23. 	}
  24. 	lens := func(i int) int { return len(e[i]) }
  26. 	for ix := make([]int, len(e)); ix[0] &lt; lens(0); NextIndex(ix, lens) {
  27. 		var r []string
  28. 		for j, k := range ix {
  29. 			r = append(r, e[j][k])
  30. 		}
  31. 		fmt.Println(r)
  32. 	}
  33. }

The output is:

  1. [a1 b1 c1 d1]
  2. [a1 b1 c2 d1]
  3. [a1 b1 c3 d1]
  4. [a1 b2 c1 d1]
  5. [a1 b2 c2 d1]
  6. [a1 b2 c3 d1]

答案2

得分: 2

根据@paul-hankin的答案，这里有一个嵌入函数并使用泛型的解决方案。需要最低的go 1.18版本。

  1. // cartesianProduct返回给定矩阵的笛卡尔积
  2. func cartesianProduct[T any](matrix [][]T) [][]T {
  3.     // nextIndex将ix设置为字典序的下一个值，
  4.     // 对于每个i>0，0 <= ix[i] < lens(i)。
  5.     nextIndex := func(ix []int, lens func(i int) int) {
  6.         for j := len(ix) - 1; j >= 0; j-- {
  7.             ix[j]++
  9.             if j == 0 || ix[j] < lens(j) {
  10.                 return
  11.             }
  13.             ix[j] = 0
  14.         }
  15.     }
  17.     lens := func(i int) int { return len(matrix[i]) }
  19.     results := make([][]T, 0, len(matrix))
  20.     for indexes := make([]int, len(matrix)); indexes[0] < lens(0); nextIndex(indexes, lens) {
  21.         var temp []T
  23.         for j, k := range indexes {
  24.             temp = append(temp, matrix[j][k])
  25.         }
  27.         results = append(results, temp)
  28.     }
  30.     return results
  31. }
英文:

Based on @paul-hankin answer, here a solution which is embedded in a function and uses generics. Needs go 1.18 minimum

  1. // cartesianProduct returns the cartesian product
  2. // of a given matrix
  3. func cartesianProduct[T any](matrix [][]T) [][]T {
  4. 	// nextIndex sets ix to the lexicographically next value,
  5. 	// such that for each i&gt;0, 0 &lt;= ix[i] &lt; lens(i).
  6. 	nextIndex := func(ix []int, lens func(i int) int) {
  7. 		for j := len(ix) - 1; j &gt;= 0; j-- {
  8. 			ix[j]++
  10. 			if j == 0 || ix[j] &lt; lens(j) {
  11. 				return
  12. 			}
  14. 			ix[j] = 0
  15. 		}
  16. 	}
  18. 	lens := func(i int) int { return len(matrix[i]) }
  20. 	results := make([][]T, 0, len(matrix))
  21. 	for indexes := make([]int, len(matrix)); indexes[0] &lt; lens(0); nextIndex(indexes, lens) {
  22. 		var temp []T
  24. 		for j, k := range indexes {
  25. 			temp = append(temp, matrix[j][k])
  26. 		}
  28. 		results = append(results, temp)
  29. 	}
  31. 	return results
  32. }

huangapple
  • 本文由 发表于 2015年3月12日 13:49:41
  • 转载请务必保留本文链接：https://go.coder-hub.com/29002724.html
  • cartesian-product
  • go
匿名

发表评论

匿名网友

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

确定