diff options
| -rw-r--r-- | lib/pure/algorithm.nim | 32 | ||||
| -rw-r--r-- | tests/stdlib/talgorithm.nim | 9 |
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]] |