How to create cartesian product [duplicate]

Question

I have a list of integers, a = [0, ..., n]. I want to generate all possible combinations of k elements from a; i.e., the cartesian product of the a with itself k times. Note that n and k are both changeable at runtime, so this needs to be at least a somewhat adjustable function.

So if n was 3, and k was 2:

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

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

In python I would use the itertools.product() function:

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

What's an idiomatic way to do this in Go?

Initial guess is a closure that returns a slice of integers, but it doesn't feel very clean.

Answer 1

For example,

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)
    }
}

Output:

[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]

Answer 2

The code to find the next product in lexicographic order is simple: starting from the right, find the first value that won't roll over when you increment it, increment that and zero the values to the right.

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]++
    }
}

I've changed "n" to mean the set is [0, 1, ..., n-1] rather than [0, 1, ..., n] as given in the question, since the latter is confusing since it has n+1 elements.