Cartesian product of arrays

Is there a standard library method to compute the cartesian product of two arrays?

I'm currently using this, works well for two arrays, but gets more complicated for more than two:

// Cartesian product of two arrays
func * <U, V>(lhs: [U], rhs: [V]) -> [(U, V)] {
    lhs.flatMap { left in
        rhs.map { right in
            (left, right)
        }
    }
}

print([1, 2, 3] * ["a", "b"])
// [(1, "a"), (1, "b"), (2, "a"), (2, "b"), (3, "a"), (3, "b")]

I believe both Python and Ruby have functions to generate cartesian products, but not sure if there is anything similar in Swift.

There is no such functionality in the standard library today, but I find myself needing it every once in a while. I feel like this is a great use case for a lazy collection wrapper similar to the one pitched in Add an `adjacentPairs` algorithm to Sequence.

If you're interested, I can post my implementation of a lazy Cartesian<Base1, Base2> tomorrow.

1 Like

I don’t think there’s anything built in. In Haskell list is a monad with cons as the bind operator, so you can do something like:

x = [1, 2, 3]

y = [a, b]

z = do i <- x ; j <- y ; return (i, j)

z

[(1,'a'),(1,'b'),(2,'a'),(2,'b'),(3,'a'),(3,'b')]

I don’t think there’s a Swift equivalent to that other than the direct method.

The below will do it with laziness, so you don’t generate the whole Cartesian product until you need it:

let a = [1, 2, 3].lazy
let b = ["a", "b", "c"].lazy

let m = a.map {num in
b.map {str in
(str, num)
}
}

for i in m {
for j in i {
print(j)
}
}

If you never get the value of j to print it, or only use the first couple, it won’t generate the rest of them. You can take out the .lazy and compare—it’s lower latency.

But flatMap is eager and will force the whole thing so you have to use map and then loop to extract the values.

For three you could do:

let a = [1, 2, 3].lazy
let b = ["a", "b", "c"].lazy
let c = [1.0, 3,0].lazy

let m = a.map {num in
b.map {str in
c.map {doub in
(str, num, doub)
}
}
}
for i in m {
for j in i {
for k in j {
print(k)
}
}
}

Hope that helps, I started thinking about this a little overnight.

—Dan

Hi, here's a sample implementation of such a CartesianProduct<Base1, Base2> wrapper:

It is quite a bit slower (~80%) than a naïve iteration using two nested loops though, I'll need to investigate that a bit more. This snippet currently only implements Sequence, it might be worth adding a Collection conformance and conditional BidirectionalCollection and RandomAccessCollection conformances as well — I'll keep the gist updated.