go/algorithm/cartesian: implement cartesian product
Change-Id: I9553266ce64a104f5b8bab2e83d9d7234994cd4b
Reviewed-on: https://review.monogon.dev/c/monogon/+/1863
Reviewed-by: Tim Windelschmidt <tim@monogon.tech>
Tested-by: Jenkins CI
diff --git a/go/algorithm/cartesian/BUILD.bazel b/go/algorithm/cartesian/BUILD.bazel
new file mode 100644
index 0000000..7495e9a
--- /dev/null
+++ b/go/algorithm/cartesian/BUILD.bazel
@@ -0,0 +1,15 @@
+load("@io_bazel_rules_go//go:def.bzl", "go_library", "go_test")
+
+go_library(
+ name = "cartesian",
+ srcs = ["cartesian.go"],
+ importpath = "source.monogon.dev/go/algorithm/cartesian",
+ visibility = ["//visibility:public"],
+)
+
+go_test(
+ name = "cartesian_test",
+ srcs = ["cartesian_test.go"],
+ embed = [":cartesian"],
+ deps = ["@com_github_google_go_cmp//cmp"],
+)
diff --git a/go/algorithm/cartesian/cartesian.go b/go/algorithm/cartesian/cartesian.go
new file mode 100644
index 0000000..fb42a2b
--- /dev/null
+++ b/go/algorithm/cartesian/cartesian.go
@@ -0,0 +1,29 @@
+package cartesian
+
+// Product returns cartesian product of arguments. Each argument must be a slice
+// of the same kind.
+func Product[T any](dimensions ...[]T) [][]T {
+ if len(dimensions) == 0 {
+ return nil
+ }
+
+ head, tail := dimensions[0], dimensions[1:]
+ tailProduct := Product[T](tail...)
+
+ var result [][]T
+ for _, v := range head {
+ if len(tailProduct) == 0 {
+ result = append(result, []T{v})
+ } else {
+ for _, ttail := range tailProduct {
+ element := []T{
+ v,
+ }
+ element = append(element, ttail...)
+ result = append(result, element)
+ }
+ }
+
+ }
+ return result
+}
diff --git a/go/algorithm/cartesian/cartesian_test.go b/go/algorithm/cartesian/cartesian_test.go
new file mode 100644
index 0000000..5911ecc
--- /dev/null
+++ b/go/algorithm/cartesian/cartesian_test.go
@@ -0,0 +1,48 @@
+package cartesian
+
+import (
+ "fmt"
+ "testing"
+
+ "github.com/google/go-cmp/cmp"
+)
+
+func TestProduct(t *testing.T) {
+ for i, te := range []struct {
+ data [][]string
+ want [][]string
+ }{
+ {
+ data: [][]string{
+ {"a", "b"},
+ {"c", "d"},
+ },
+ want: [][]string{
+ {"a", "c"},
+ {"a", "d"},
+ {"b", "c"},
+ {"b", "d"},
+ },
+ },
+ {
+ data: [][]string{
+ {"a", "b"},
+ },
+ want: [][]string{
+ {"a"},
+ {"b"},
+ },
+ },
+ {
+ data: [][]string{},
+ want: nil,
+ },
+ } {
+ t.Run(fmt.Sprintf("%d", i), func(t *testing.T) {
+ got := Product(te.data...)
+ if diff := cmp.Diff(te.want, got); diff != "" {
+ t.Fatalf("Diff:\n%s", diff)
+ }
+ })
+ }
+}