added Cartesian product

2 files changed, 41 insertions, 0 deletions

diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim
index df7ae6d17..2620f7c90 100644
--- a/lib/pure/algorithm.nim
+++ b/lib/pure/algorithm.nim
@@ -131,3 +131,35 @@ proc sort*[T](a: var openArray[T],
       dec(m, s*2)
     s = s*2
 
+proc product[T](x: openarray[seq[T]]): seq[seq[T]] =
+  ## produces the Cartesian product of the array. Warning: complexity
+  ## may explode.
+  result = @[]
+  if x.len == 0:
+    return
+  if x.len == 1:
+    result = @x
+    return
+  var
+    indexes = newSeq[int](x.len)
+    initial = newSeq[int](x.len)
+    index = 0
+  # replace with newSeq as soon as #853 is fixed
+  var next: seq[T] = @[]
+  next.setLen(x.len)
+  for i in 0..(x.len-1):
+    initial[i] = len(x[i])-1
+  indexes = initial
+  while true:
+    while indexes[index] == -1:
+      indexes[index] = initial[index]
+      index +=1
+      if index == x.len: return
+      indexes[index] -=1
+    for ni, i in indexes:
+      next[ni] = x[ni][i]
+    var res: seq[T]
+    shallowCopy(res, next)
+    result.add(res)
+    index = 0
+    indexes[index] -=1
diff --git a/tests/stdlib/talgorithm.nim b/tests/stdlib/talgorithm.nim
new file mode 100644
index 000000000..ea57883b0
--- /dev/null
+++ b/tests/stdlib/talgorithm.nim
@@ -0,0 +1,9 @@
+import unittest
+
+suite "product":
+  test "a simple case of one element":
+    check product(@[@[1,2]]) == @[@[1,2]]
+  test "two elements":
+    check product(@[@[1,2], @[3,4]]) == @[@[2,4],@[1,4],@[2,3],@[1,3]]
+  test "three elements":
+    check product(@[@[1,2], @[3,4], @[5,6]]) == @[@[2,4,6],@[1,4,6],@[2,3,6],@[1,3,6], @[2,4,5],@[1,4,5],@[2,3,5],@[1,3,5]]