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