Cartesian product of arrays

Using Swift
1

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.

2

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.

2 Likes
3

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

4

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.

5

I have rolled one up today after I was unable to find one in Swift Algorithms.

Details
Cartesian Product 
//
//  CartesianProduct.swift
//  CartesianProduct
//
//  Created by ibex10 on 23/11/2022.
//

// -------------------------------------------------------------
//
class CartesianProduct {
    private let head  : Range <Int>
    private var tail  : CartesianProduct?
    private var index : Range <Int>.Index
    
    init (_ head: Range <Int>, _ tail: CartesianProduct? = nil) {
        self.head  = head
        self.tail  = tail
        self.index = head.startIndex
    }
    
    func append (range: Range <Int>) {
        if let tail {
            tail.append (range: range)
        }
        else {
            tail = CartesianProduct (range)
        }
    }
    
    func next () -> [Int]? {
        guard index != head.endIndex else {
            return nil
        }
        
        var u = [Int] ()
        u.append (head [index])
        guard let tail else {
            _ = move ()
            return u
        }
        if let v = tail.next () {
            u.append (contentsOf: v)
            return u
        }
        else {
            tail.restart ()
            if move () {
                return next ()
            }
        }
        assert (!u.isEmpty)
        return u
    }
}

// -------------------------------------------------------------
//
extension CartesianProduct {
    private func move () -> Bool {
        guard self.index != head.endIndex else {
            return false
        }
        self.index = head.index (after: index)
        return true
    }
    
    private func restart () {
        self.index = head.startIndex
        if let tail {
            tail.restart()
        }
    }
}
Test Driver 
//
//  main.swift
//  CartesianProduct
//
//  Created by ibex10 on 23/11/2022.
//

let product = CartesianProduct (Range (0...1))
if true {
    product.append (range: Range (0...2))
    product.append (range: Range (0...3))
    product.append (range: Range (0...4))
}
while let v = product.next () {
    print (v)
}

My algorithm generates the cartesian product of a sequence of ranges. The integers in the resulting product can then be used to index into arrays of other things.

let product = CartesianProduct (Range (0...1))
if true {
    product.append (range: Range (0...1))
    product.append (range: Range (0...2))
}
while let v = product.next () {
    print (v)
}

// Produces the output
[0, 0, 0]
[0, 0, 1]
[0, 0, 2]
[0, 1, 0]
[0, 1, 1]
[0, 1, 2]
[1, 0, 0]
[1, 0, 1]
[1, 0, 2]
[1, 1, 0]
[1, 1, 1]
[1, 1, 2]

Looking forward to receiving feedback. :grin:

6
3 Likes
7

Thank you, @anon9791410

I can't believe I have missed the product function. :frowning:

The product function produces tuples of tuples when more than two sets are involved.

For example:

import Algorithms

let s1 = 0...1
let s2 = 0...1
let s3 = 0...1
let s4 = 0...1

let p1 = product (s1, s2)
let p2 = product (p1, s3)
let p3 = product (p2, s4)

for p in p3 {
    print (p)
}

The output of that code is a sequence of tuples of tuples.

(((0, 0), 0), 0)
(((0, 0), 0), 1)
(((0, 0), 1), 0)
(((0, 0), 1), 1)
(((0, 1), 0), 0)
(((0, 1), 0), 1)
(((0, 1), 1), 0)
(((0, 1), 1), 1)
(((1, 0), 0), 0)
(((1, 0), 0), 1)
(((1, 0), 1), 0)
(((1, 0), 1), 1)
(((1, 1), 0), 0)
(((1, 1), 0), 1)
(((1, 1), 1), 0)
(((1, 1), 1), 1)

Is there an easy way get a sequence of flat arrays instead?

[0, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 1, 0]
[0, 0, 1, 1]
[0, 1, 0, 0]
[0, 1, 0, 1]
[0, 1, 1, 0]
[0, 1, 1, 1]
[1, 0, 0, 0]
[1, 0, 0, 1]
[1, 0, 1, 0]
[1, 0, 1, 1]
[1, 1, 0, 0]
[1, 1, 0, 1]
[1, 1, 1, 0]
[1, 1, 1, 1]
8

Variadic generics will make this better. For now, just keep overloading for as deep an arity as you need. I think bigger tuples make sense, but return arrays if you want, or use a conversion.

@inlinable public func product<Base1: Collection, Base2: Collection, Base3: Collection>(
  _ s1: Base1, _ s2: Base2, _ s3: Base3
) -> some Collection<(Base1.Element, Base2.Element, Base3.Element)> {
  product(s1, product(s2, s3)).lazy.map { ($0, $1.0, $1.1) }
}

@inlinable public func product<
  Base1: Collection, Base2: Collection, Base3: Collection, Base4: Collection
>(
  _ s1: Base1, _ s2: Base2, _ s3: Base3, _ s4: Base4
) -> some Collection<(Base1.Element, Base2.Element, Base3.Element, Base4.Element)> {
  product(s1, product(s2, s3, s4)).lazy.map { ($0, $1.0, $1.1, $1.2) }
}

public extension Array {
  /// Create an `Array` if `subject's` values are all of one type.
  /// - Note: Useful for converting tuples to `Array`s.
  init?<Subject>(mirrorChildValuesOf subject: Subject) {
    guard let array =
      Mirror(reflecting: subject).children.map(\.value)
      as? Self
    else { return nil }

    self = array
  }
}
9

Just tried to program this with variadic generics, couldn't do it :( It appears that variadic generics are currently designed for "map"-style problems, but this appears to be a "reduce"-style problem. Either I'm stupid or we need further progress