如何创建笛卡尔积

Question

我有一个整数列表，a = [0, ..., n]。我想要生成所有可能的由 k 个元素组成的组合；即，将 a 自己与自己 k 次进行笛卡尔积操作。请注意，n 和 k 都可以在运行时更改，因此这需要是至少有一定可调性的函数。

所以，如果 n 是 3，k 是 2：

a = [0, 1, 2, 3]
k = 2

desired = [(0,0), (0, 1), (0, 2), ..., (2,3), (3,0), ..., (3,3)]

在Python中，我会使用itertools.product()函数：

for p in itertools.product(a, repeat=2):
    print p

在Go中，有什么惯用的方法来做这个？

初步猜测是一个返回整数切片的闭包，但感觉不太规范。

- chmullig

Answer 1

例如，

package main

import "fmt"

func nextProduct(a []int, r int) func() []int {
    p := make([]int, r)
    x := make([]int, len(p))
    return func() []int {
        p := p[:len(x)]
        for i, xi := range x {
            p[i] = a[xi]
        }
        for i := len(x) - 1; i >= 0; i-- {
            x[i]++
            if x[i] < len(a) {
                break
            }
            x[i] = 0
            if i <= 0 {
                x = x[0:0]
                break
            }
        }
        return p
    }
}

func main() {
    a := []int{0, 1, 2, 3}
    k := 2
    np := nextProduct(a, k)
    for {
        product := np()
        if len(product) == 0 {
            break
        }
        fmt.Println(product)
    }
}

输出：

[0 0]
[0 1]
[0 2]
[0 3]
[1 0]
[1 1]
[1 2]
[1 3]
[2 0]
[2 1]
[2 2]
[2 3]
[3 0]
[3 1]
[3 2]
[3 3]

- peterSO

---

即将返回并发布类似的内容。这是一个漂亮的单一函数算法 http://play.golang.org/p/qkr5BUMpGT - JimB

@JimB: Python: itertools — Functions creating iterators for efficient looping: memory efficient tools。你的内存使用效率不高。 - peterSO

没错，我并没有考虑复制Python生成器，只是想复制算法。 - JimB

Answer 2

查找字典顺序下一个产品的代码很简单：从右边开始，找到第一个在增加时不会翻转的值，将其增加并将右侧的值清零。

package main

import "fmt"

func main() {
    n, k := 5, 2
    ix := make([]int, k)
    for {
        fmt.Println(ix)
        j := k - 1
        for ; j >= 0 && ix[j] == n-1; j-- {
            ix[j] = 0
        }
        if j < 0 {
            return
        }
        ix[j]++
    }
}

我已经将“n”更改为表示集合[0, 1, ..., n-1]，而不是题目中给出的[0, 1, ..., n]，因为后者很容易混淆，因为它有n + 1个元素。

- Paul Hankin

Answer 3

只需按照答案在Go中实现Ruby风格的笛卡尔积, 在http://play.golang.org/p/NR1_3Fsq8F上运行即可。

package main

import "fmt"

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

func main() {
    a := []int{0, 1, 2, 3}
    k := 2
    lens := len(a)
    r := make([]int, k)
    for ix := make([]int, k); ix[0] < lens; NextIndex(ix, lens) {
        for i, j := range ix {
            r[i] = a[j]
        }
        fmt.Println(r)
    }
}

- Daniel YC Lin