# Cartesian product of arrays

**URL:** <https://forums.swift.org/t/cartesian-product-of-arrays/37203>\
**Category:** Using Swift\
**Created:** [June 3, 2020, 9:56pm UTC](https://forums.swift.org/t/cartesian-product-of-arrays/37203 "2020-06-03T21:56:08Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![eneko](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/eneko/32/12117_2.png) [@eneko](https://forums.swift.org/u/eneko)\
**Post date:** [June 3, 2020, 9:56pm UTC](https://forums.swift.org/t/cartesian-product-of-arrays/37203/1 "2020-06-03T21:56:09Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![jenox](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/jenox/32/5811_2.png) [@jenox](https://forums.swift.org/u/jenox)\
**Post date:** [June 3, 2020, 11:05pm UTC](https://forums.swift.org/t/cartesian-product-of-arrays/37203/2 "2020-06-03T23:05:42Z")

</div>

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](https://forums.swift.org/t/add-an-adjacentpairs-algorithm-to-sequence/14817/).

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

---

<div class="post-metadata">

**Author:** ![dfsweeney](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/dfsweeney/32/12031_2.png) [@dfsweeney](https://forums.swift.org/u/dfsweeney)\
**Post date:** [June 4, 2020, 7:59pm UTC](https://forums.swift.org/t/cartesian-product-of-arrays/37203/3 "2020-06-04T19:59:07Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![jenox](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/jenox/32/5811_2.png) [@jenox](https://forums.swift.org/u/jenox)\
**Post date:** [June 4, 2020, 9:29pm UTC](https://forums.swift.org/t/cartesian-product-of-arrays/37203/4 "2020-06-04T21:29:27Z")

</div>

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

> <https://gist.github.com/jenox/788495f449ff3a22f272e627b20933af>

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.

---

<div class="post-metadata">

**Author:** ![ibex](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ibex/32/30439_2.png) [@ibex](https://forums.swift.org/u/ibex)\
**Post date:** [November 23, 2022, 10:49am UTC](https://forums.swift.org/t/cartesian-product-of-arrays/37203/5 "2022-11-23T10:49:26Z")

</div>

I have rolled one up today after I was unable to find one in [Swift Algorithms](https://github.com/apple/swift-algorithms).

> **Details**
>
> > **Cartesian Product**
> >
> > ```swift
> > //
> > // 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**
> >
> > ```swift
> > //
> > // 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.

```swift
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)
}

```

```swift
// 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. 😁

---

<div class="post-metadata">

**Author:** ![anon9791410](https://avatars.discourse-cdn.com/v4/letter/a/9fc348/32.png) [@anon9791410](https://forums.swift.org/u/anon9791410)\
**Post date:** [November 23, 2022, 12:47pm UTC](https://forums.swift.org/t/cartesian-product-of-arrays/37203/6 "2022-11-23T12:47:36Z")

</div>

> [@ibex](#):
>
> I have rolled one up today after I was unable to find one in [Swift Algorithms](https://github.com/apple/swift-algorithms).

> [@](#):
>
> This function and the resulting collection provide the cartesian product of two collections.

> <https://github.com/apple/swift-algorithms/blob/main/Guides/Product.md>

---

<div class="post-metadata">

**Author:** ![ibex](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ibex/32/30439_2.png) [@ibex](https://forums.swift.org/u/ibex)\
**Post date:** [November 23, 2022, 11:35pm UTC](https://forums.swift.org/t/cartesian-product-of-arrays/37203/7 "2022-11-23T23:35:18Z")

</div>

Thank you, @anon9791410

I can't believe I have missed the `product` function. ☹

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

For example:

```swift
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.

```swift
(((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?

```swift
[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]

```

---

<div class="post-metadata">

**Author:** ![anon9791410](https://avatars.discourse-cdn.com/v4/letter/a/9fc348/32.png) [@anon9791410](https://forums.swift.org/u/anon9791410)\
**Post date:** [November 24, 2022, 2:50am UTC](https://forums.swift.org/t/cartesian-product-of-arrays/37203/8 "2022-11-24T02:50:47Z")

</div>

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.

```swift
@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) }
}

```

```swift
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
  }
}

```

---

<div class="post-metadata">

**Author:** ![Anachron](https://avatars.discourse-cdn.com/v4/letter/a/bc8723/32.png) [@Anachron](https://forums.swift.org/u/Anachron)\
**Post date:** [September 27, 2023, 10:22pm UTC](https://forums.swift.org/t/cartesian-product-of-arrays/37203/9 "2023-09-27T22:22:11Z")

</div>

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