怎么用 golang 搞一个 [多维的笛卡尔积] 呀？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

The Go Programming Language

› http://golang.org/

› Go Playground

Go Projects

› Revel Web Framework

这是一个创建于 1397 天前的主题，其中的信息可能已经有所发展或是发生改变。

有这么个需求，给一组维度，维度的数量不固定，各个维度的取值数目也不一定。类似

di: 0, 1, 2 
dj: 0, 1
dk: 0, 1, 2, 3, 4
...

怎么取得这么一组给定不定长维度下值的组合？

# example
package main

import "fmt"

var (
	di = []int{0, 1, 2}
	dj = []int{0, 1}
	dk = []int{0, 1, 2, 3, 4}
)

func main() {
	getResult(di, dj, dk)
}

func getResult(di, dj, dk []int) {
	for _, i := range di {
		for _, j := range dj {
			for _, k := range dk {
				fmt.Printf("[%d, %d, %d] \t", i, j, k)
			}
		}
	}
}

# result
[0, 0, 0] 	[0, 0, 1] 	[0, 0, 2] 	[0, 0, 3] 	[0, 0, 4] 	[0, 1, 0] 	[0, 1, 1] 	[0, 1, 2] 	[0, 1, 3] 	[0, 1, 4] 	[1, 0, 0] 	[1, 0, 1] 	[1, 0, 2] 	[1, 0, 3] 	[1, 0, 4] 	[1, 1, 0] 	[1, 1, 1] 	[1, 1, 2] 	[1, 1, 3] 	[1, 1, 4] 	[2, 0, 0] 	[2, 0, 1] 	[2, 0, 2] 	[2, 0, 3] 	[2, 0, 4] 	[2, 1, 0] 	[2, 1, 1] 	[2, 1, 2] 	[2, 1, 3] 	[2, 1, 4]

如果维度再增加，还得手动加上一套for range。有没有更好的解决方案？

int

range

维度

for

15 条回复 • 2021-02-01 12:50:25 +08:00

misdake

2021-01-31 21:26:35 +08:00

和指定长度数组的全排列蛮像的，循环的层数是不确定的，只是取数字的方式不一样

zhoudaiyu

2021-01-31 21:29:58 +08:00 via iPhone

是不是可以考虑用代码生成代码的思路？

fline

2021-01-31 21:31:28 +08:00

递归

minbaby

2021-01-31 21:41:51 +08:00

https://github.com/emirpasic/gods

这个可以看看

chairuosen

2021-01-31 21:47:42 +08:00

只写一层 for，自己判断跳出条件和累加策略

notamail

2021-01-31 22:03:04 +08:00

@fline +1

notamail

2021-01-31 22:03:39 +08:00

应该没有你这样写代码的。。。

Lemeng

2021-01-31 22:05:30 +08:00

for 有点多

jinliming2

2021-01-31 22:12:36 +08:00

不一定是最高效的办法：
```go
package main

import "fmt"

var (
di = []int{0, 1, 2}
dj = []int{0, 1}
dk = []int{0, 1, 2, 3, 4}
)

func main() {
res := getResult(di, dj, dk)
for _, item := range res {
fmt.Println(item)
}
}

func getResult(d0 []int, d1 ...[]int) (res [][]int) {
if len(d1) == 0 {
res = make([][]int, 0, len(d0))
for _, d := range d0 {
res = append(res, []int{d})
}
return
}
sub := getResult(d1[0], d1[1:]...)
for _, item := range d0 {
for _, s := range sub {
c := []int{item}
c = append(c, s...)
res = append(res, c)
}
}
return
}
```

Claar

2021-01-31 22:55:52 +08:00 via iPhone

哈哈哈看来 V2EX 的少年算法水平不行啊
这看起来是求全排列吗？
最基本的解决方案可以看基础的算法里的暴力破解，不剪枝
手机登的 V2EX 没法发代码……图片也不知道咋发

Claar

2021-01-31 23:07:32 +08:00

"""
func main() {
input := [][]int{[]int{1, 2, 3, }, []int{5, 6, 7, 8}, []int{9, 10, 11, 12}}
res := make([][]int, 0)
rec := make([]int, 0)
helper(input, &res, &rec, 0)
fmt.Println(res)

}

func helper(input [][]int, res *[][]int, rec *[]int, index int) {
if index < len(input) {
for _, v := range input[index] {
*rec = append(*rec, v)
helper(input, res, rec, index+1)
*rec = (*rec)[:index]
}
return
}
tmp := make([]int, len(input))
copy(tmp, *rec)
*res = append(*res, tmp)
*rec = (*rec)[:index]
}

"""

crclz

2021-01-31 23:08:17 +08:00

基础的 DFS

lu5je0

2021-01-31 23:08:46 +08:00

```java
class Demo {

public static void main(String[] args) {
new Demo().func();
}

public void func() {
List<List<Integer>> res = new ArrayList<>();
List<List<Integer>> sourceList = new ArrayList<>();
sourceList.add(Arrays.asList(0, 1, 2));
sourceList.add(Arrays.asList(0, 1));
sourceList.add(Arrays.asList(0, 1, 2, 3, 4));
dfs(sourceList, res, new ArrayList<>(), 0);
System.out.println(res);
}

public void dfs(List<List<Integer>> sourceList, List<List<Integer>> res, List<Integer> curList, int index) {
if (index == sourceList.size()) {
res.add(new ArrayList<>(curList));
} else {
List<Integer> source = sourceList.get(index);
for (Integer i : source) {
curList.add(i);
dfs(sourceList, res, curList, index + 1);
curList.remove(curList.size() - 1);
}

}
}

}
```

mauve

2021-02-01 08:20:01 +08:00 via iPhone

builtin 的 append 方法就是用的 for 循环

DarkCat123

2021-02-01 12:50:25 +08:00

康托展开。