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

Question

我想要获得 a, b, c, d 的笛卡尔积：

a = ['a1']
b = ['b1', 'b2']
c = ['c1', 'c2', 'c3']
d = ['d1']

以下是Ruby代码:

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

输出结果为：

[
  ["a1", "b1", "c1", "d1"],
  ["a1", "b1", "c2", "d1"],
  ["a1", "b1", "c3", "d1"],
  ["a1", "b2", "c1", "d1"],
  ["a1", "b2", "c2", "d1"],
  ["a1", "b2", "c3", "d1"]
]

是否有类似的包或函数可以在Golang中进行乘积运算？ 这只是一个简化版本，实际输入数据类似于[['a1'],['b1','b2'],['c1','c2','c3'],['d1'],['e1',...],...]。

- Daniel YC Lin

---

是的：三个嵌套的for循环。 - Volker

你可以在godoc.org或go-search.org上寻找矩阵包。 - Dave C

Answer 1

如果您需要在编译时不确定嵌套索引循环的集合，可以使用以下代码。

package main

import "fmt"

// NextIndex sets ix to the lexicographically next value,
// such that for each i>0, 0 <= ix[i] < lens(i).
func NextIndex(ix []int, lens func(i int) int) {
    for j := len(ix) - 1; j >= 0; j-- {
        ix[j]++
        if j == 0 || ix[j] < lens(j) {
            return
        }
        ix[j] = 0
    }
}

func main() {
    e := [][]string{
        {"a1"},
        {"b1", "b2"},
        {"c1", "c2", "c3"},
        {"d1"},
    }
    lens := func(i int) int { return len(e[i]) }

    for ix := make([]int, len(e)); ix[0] < lens(0); NextIndex(ix, lens) {
        var r []string
        for j, k := range ix {
            r = append(r, e[j][k])
        }
        fmt.Println(r)
    }
}

输出结果如下：

[a1 b1 c1 d1]
[a1 b1 c2 d1]
[a1 b1 c3 d1]
[a1 b2 c1 d1]
[a1 b2 c2 d1]
[a1 b2 c3 d1]

- Paul Hankin

Answer 2

根据@paul-hankin的回答，这里提供了一个嵌入函数并使用泛型的解决方案。需要至少go 1.18版本。

// cartesianProduct returns the cartesian product
// of a given matrix
func cartesianProduct[T any](matrix [][]T) [][]T {
    // nextIndex sets ix to the lexicographically next value,
    // such that for each i>0, 0 <= ix[i] < lens(i).
    nextIndex := func(ix []int, lens func(i int) int) {
        for j := len(ix) - 1; j >= 0; j-- {
            ix[j]++

            if j == 0 || ix[j] < lens(j) {
                return
            }

            ix[j] = 0
        }
    }

    lens := func(i int) int { return len(matrix[i]) }

    results := make([][]T, 0, len(matrix))
    for indexes := make([]int, len(matrix)); indexes[0] < lens(0); nextIndex(indexes, lens) {
        var temp []T

        for j, k := range indexes {
            temp = append(temp, matrix[j][k])
        }

        results = append(results, temp)
    }

    return results
}

- saniales