V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
The Go Programming Language
http://golang.org/
Go Playground
Go Projects
Revel Web Framework
suueyoung
V2EX  ›  Go 编程语言

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

  •  
  •   suueyoung · 2021-01-31 20:58:27 +08:00 · 2856 次点击
    这是一个创建于 1376 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    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。 有没有更好的解决方案?

    15 条回复    2021-02-01 12:50:25 +08:00
    misdake
        1
    misdake  
       2021-01-31 21:26:35 +08:00
    和指定长度数组的全排列蛮像的,循环的层数是不确定的,只是取数字的方式不一样
    zhoudaiyu
        2
    zhoudaiyu  
       2021-01-31 21:29:58 +08:00 via iPhone
    是不是可以考虑用代码生成代码的思路?
    fline
        3
    fline  
       2021-01-31 21:31:28 +08:00
    递归
    minbaby
        4
    minbaby  
       2021-01-31 21:41:51 +08:00
    chairuosen
        5
    chairuosen  
       2021-01-31 21:47:42 +08:00
    只写一层 for,自己判断跳出条件和累加策略
    notamail
        6
    notamail  
       2021-01-31 22:03:04 +08:00
    @fline +1
    notamail
        7
    notamail  
       2021-01-31 22:03:39 +08:00
    应该没有你这样写代码的。。。
    Lemeng
        8
    Lemeng  
       2021-01-31 22:05:30 +08:00
    for 有点多
    jinliming2
        9
    jinliming2  
       2021-01-31 22:12:36 +08:00   ❤️ 1
    不一定是最高效的办法:
    ```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
        10
    Claar  
       2021-01-31 22:55:52 +08:00 via iPhone
    哈哈哈看来 V2EX 的少年算法水平不行啊
    这看起来是求全排列吗?
    最基本的解决方案可以看基础的算法里的暴力破解,不剪枝
    手机登的 V2EX 没法发代码……图片也不知道咋发
    Claar
        11
    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
        12
    crclz  
       2021-01-31 23:08:17 +08:00
    基础的 DFS
    lu5je0
        13
    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
        14
    mauve  
       2021-02-01 08:20:01 +08:00 via iPhone
    builtin 的 append 方法就是用的 for 循环
    DarkCat123
        15
    DarkCat123  
       2021-02-01 12:50:25 +08:00
    康托展开。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1029 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 20:33 · PVG 04:33 · LAX 12:33 · JFK 15:33
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.