1 files changed, 33 insertions, 0 deletions
diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim
index df7ae6d17..921c659de 100644
--- a/lib/pure/algorithm.nim
+++ b/lib/pure/algorithm.nim
@@ -131,3 +131,36 @@ 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):
+    if len(x[i]) == 0: return
+    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