Go手習い１：デカルト積（直積）

背景

今回はデカルト積（直積）を書いてみる。
複数個の配列（正確にはスライス）からそれぞれ一つの要素を取り出して全ての組合せを作成する。

実装１：後ろから前に結果を作る。

再帰関数で実装する。最後の配列までたどり着いたら一旦{nil}で返し、一階層ずつ戻りながら後ろから逆順に結果を作成する。
例えば、{{1, 2, 3}, {4, 5}, {6, 7}}の直積はこんな感じで結果にたどりつく。
{nil}
=> {{6},{7}}
=> {{4,6},{4,7},{5,6},{5,7}}
=> {{1,4,6},{1,4,7},{1,5,6},{1,5,7},{2,4,6},{2,4,7},{2,5,6},{2,5,7},{3,4,6},{3,4,7},{3,5,6},{3,5,7}}

cartesian.go

package main

import "fmt"

func cartesian(list [][]interface{}) [][]interface{} {
        return cartesianHelper(0, list)
}

func cartesianHelper(n int, list [][]interface{}) [][]interface{} {
        var result [][]interface{}

        if n == len(list) {
                result = [][]interface{}{nil}
        } else {
                for _, e := range list[n] {
                        for _, r := range cartesianHelper(n+1, list) {
                                s := []interface{}{e}
                                s = append(s, r...)
                                result = append(result, s)
                        }
                }
        }
        return result
}

func main() {
        var list [][]interface{}
        var result [][]interface{}

        list = [][]interface{}{{1, 2, 3}, {4, 5}, {6, 7}}
        result = cartesian(list)
        fmt.Println("list:", list)
        fmt.Println("result:", result)

        list = [][]interface{}{{"xxx", "yyy"}, {"aaa", "bbb"}}
        result = cartesian(list)
        fmt.Println("list:", list)
        fmt.Println("result:", result)
}

わからないこと

• 結果を作成するところで s = append(s, r...) は後ろにスライスをコピーするので遅そう。

実装２：前から後ろに結果を作る。

同じく再帰関数だが、今度は前から順に結果を作りながら後ろに渡す。最後までたどり着いたらそれが結果となる。
例えば、{{1, 2, 3}, {4, 5}, {6, 7}}の直積はこんな感じで結果にたどりつく。
{nil}
=> {{1},{2},{3}}
=> {{1,4},{1,5},{2,4},{2,5},{3,4},{3,5}}
=> {{1,4,6},{1,4,7},{1,5,6},{1,5,7},{2,4,6},{2,4,7},{2,5,6},{2,5,7},{3,4,6},{3,4,7},{3,5,6},{3,5,7}}
結果を貯め込んで引数として再帰的に渡す必要がある。このためヘルパー関数でかぶせる。

cartesian2.go

package main

import "fmt"

func cartesian(list [][]interface{}) [][]interface{} {
        return (cartesianHelper(list, [][]interface{}{nil}))
}

func cartesianHelper(list [][]interface{}, result [][]interface{}) [][]interface{} {
        if 0 == len(list) {
                return result
        }
        var s [][]interface{}
        for _, r := range result {
                for _, e := range list[0] {
                        s = append(s, append(r, e))
                }
        }
        return cartesianHelper(list[1:], s)
}

func main() {
        var list [][]interface{}
        var result [][]interface{}

        list = [][]interface{}{{1, 2, 3}, {4, 5}, {6, 7}}
        result = cartesian(list)
        fmt.Println("list:", list)
        fmt.Println("result:", result)

        list = [][]interface{}{{"xxx", "yyy"}, {"aaa", "bbb"}}
        result = cartesian(list)
        fmt.Println("list:", list)
        fmt.Println("result:", result)
}

わからないこと

• 末尾再帰は動作時にgotoになるのか？