Cartesian product of two or more lists
In Sidef, the Cartesian product of an arbitrary number of arrays is built-in as Array.cartesian():
cartesian([[1,2], [3,4], [5,6]]).say
cartesian([[1,2], [3,4], [5,6]], {|*arr| say arr })
Alternatively, a simple recursive implementation:
func cartesian_product(*arr) {
var c = []
var r = []
func {
if (c.len < arr.len) {
for item in (arr[c.len]) {
c.push(item)
__FUNC__()
c.pop
}
}
else {
r.push([c...])
}
}()
return r
}
Completing the task:
say cartesian_product([1,2], [3,4])
say cartesian_product([3,4], [1,2])
Output:
[[1, 3], [1, 4], [2, 3], [2, 4]]
[[3, 1], [3, 2], [4, 1], [4, 2]]
The product of an empty list with any other list is empty:
say cartesian_product([1,2], [])
say cartesian_product([], [1,2])
Output:
[]
[]
Extra credit:
cartesian_product([1776, 1789], [7, 12], [4, 14, 23], [0, 1]).each{ .say }
Output:
[1776, 7, 4, 0]
[1776, 7, 4, 1]
[1776, 7, 14, 0]
[1776, 7, 14, 1]
[1776, 7, 23, 0]
[1776, 7, 23, 1]
[1776, 12, 4, 0]
[1776, 12, 4, 1]
[1776, 12, 14, 0]
[1776, 12, 14, 1]
[1776, 12, 23, 0]
[1776, 12, 23, 1]
[1789, 7, 4, 0]
[1789, 7, 4, 1]
[1789, 7, 14, 0]
[1789, 7, 14, 1]
[1789, 7, 23, 0]
[1789, 7, 23, 1]
[1789, 12, 4, 0]
[1789, 12, 4, 1]
[1789, 12, 14, 0]
[1789, 12, 14, 1]
[1789, 12, 23, 0]
[1789, 12, 23, 1]
say cartesian_product([1, 2, 3], [30], [500, 100])
say cartesian_product([1, 2, 3], [], [500, 100])
Output:
[[1, 30, 500], [1, 30, 100], [2, 30, 500], [2, 30, 100], [3, 30, 500], [3, 30, 100]]
[]