Given
[0, 1]
What is this called?
[[0, 0], [0, 1], [1, 0], [1, 1]]
I don't see any option which does this. Only this subset is provided:
[[0, 1], [1, 0]]
1 Like
Try the Cartesian product(_:_:) with the same argument twice.
2 Likes
No, that only works when the collection is two elements long.
The combination count needs to scale as a power of two, representing, for example, corner points of "rectangles" of various dimensions.
let rect = Rect3D(origin: .zero, size: .one)
let min = rect.min
let max = rect.max
#expect(
Set(rect.cornerPoints) ==
[ .init(x: min.x, y: min.y, z: min.z),
.init(x: min.x, y: min.y, z: max.z),
.init(x: min.x, y: max.y, z: min.z),
.init(x: min.x, y: max.y, z: max.z),
.init(x: max.x, y: min.y, z: min.z),
.init(x: max.x, y: min.y, z: max.z),
.init(x: max.x, y: max.y, z: min.z),
.init(x: max.x, y: max.y, z: max.z),
]
)
1 Like
As @pyrtsa said, it is the cartesian product (in the latter case the n-ary cartesian product). For the example you provided, where the collections are arrays of the same type, you can naively define your own variadic product function, e.g.
func product<Element>(_ collections: [Element]...) -> [[Element]] {
guard let first = collections.first?.map({ [$0] }) else { return [] }
return collections[1...].reduce(first) { partialResult, next in
partialResult.flatMap { row in
next.map { element in row + [element] }
}
}
}
Your latter example would then be:
product([min.x, max.x], [min.y, max.y], [min.z, max.z])
A better approach would require creating ProductSequence and ProductSequence.Iterator, following how product(_:_:) and all the other Swift Algorithms have been implemented.
Not quite, in the general case, the cartesian product count is the product of the of the counts of the sets involved.
A relevant topic:
2 Likes
In the general case, you would need a variadic version of product(_:_:), but so far there's none in swift-algorithms. (I don't know if parameter packs are feature complete enough that it could be implemented.)
But you don't strictly need that complexity, because at the cost of a few nested trailing closures, you can achieve the same with Array.flatMap calls and a single map:
struct Point3D {
var x, y, z: Int
}
struct Rect3D {
var min, max: Point3D
var cornerPoints: [Point3D] {
let extrema = [min, max]
let xs = extrema.map(\.x)
let ys = extrema.map(\.y)
let zs = extrema.map(\.z)
return xs.flatMap { x in ys.flatMap { y in zs.map { z in
Point3D(x: x, y: y, z: z)
}}}
// with hypothetical variadic `product(...)`:
// return product(xs, ys, zs).map { x, y, z in
// Point3D(x: x, y: y, z: z)
// }
}
}
I couldn't resist digging up something I have done ages ago. :)
It can compute the cartesian product of integer ranges.
// {0, 1, 2} x {3, 4} x {5, 6, 7}
let product = CartesianProduct (0..<3)
product.append (range: 3..<5)
product.append (range: 5..<8)
while let v = product.next () {
print (v)
}
Cartesian Product
//
// CartesianProduct.swift
//
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
}
}
extension CartesianProduct {
func append (range: Range <Int>) {
if let tail {
tail.append (range: range)
}
else {
tail = CartesianProduct (range)
}
}
}
extension CartesianProduct {
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()
}
}
}
Driver
// Driver.swift
@main
enum Driver {
static func main () {
test1 ()
print ()
test2 ()
}
}
private
extension Driver {
static func test1 () {
// {0, 1, 2} x {3, 4} x {5, 6, 7}
let product = CartesianProduct (0..<3)
product.append (range: 3..<5)
product.append (range: 5..<8)
while let v = product.next () {
print (v)
}
}
}
private
extension Driver {
static func test2 () {
// {red, green, blue} x {mint, teal} x {0, 1, 2}
let s0: [String] = ["red", "green", "blue"]
let s1: [String] = ["mint", "teal"]
let s2: [Int] = [0, 1, 2]
let f0 = {(i: Int) in s0 [i]}
let f1 = {(i: Int) in s1 [i]}
let f2 = {(i: Int) in s2 [i]}
let product = CartesianProduct (0..<s0.count)
product.append (range: 0..<s1.count)
product.append (range: 0..<s2.count)
let fv: [(Int) -> Any] = [f0, f1, f2]
while let v = product.next () {
// map indices to corresponding values
var x = 0
var mv: [Any] = []
for i in v {
mv.append ((fv [x])(i))
x += 1
}
print (mv, separator: ", ", terminator: "")
print ()
mv = []
}
}
}
// {0, 1, 2} x {3, 4} x {5, 6, 7}
[0, 3, 5]
[0, 3, 6]
[0, 3, 7]
[0, 4, 5]
[0, 4, 6]
[0, 4, 7]
[1, 3, 5]
[1, 3, 6]
[1, 3, 7]
[1, 4, 5]
[1, 4, 6]
[1, 4, 7]
[2, 3, 5]
[2, 3, 6]
[2, 3, 7]
[2, 4, 5]
[2, 4, 6]
[2, 4, 7]
// {red, green, blue} x {mint, teal} x {0, 1, 2}
["red", "mint", 0]
["red", "mint", 1]
["red", "mint", 2]
["red", "teal", 0]
["red", "teal", 1]
["red", "teal", 2]
["green", "mint", 0]
["green", "mint", 1]
["green", "mint", 2]
["green", "teal", 0]
["green", "teal", 1]
["green", "teal", 2]
["blue", "mint", 0]
["blue", "mint", 1]
["blue", "mint", 2]
["blue", "teal", 0]
["blue", "teal", 1]
["blue", "teal", 2]
2 Likes
Yeah, if efficiency is important, I would implement this as a stream instead of computing n products and throwing out all intermediate results except for the final one.
That is, instead of approaching this problem as one where you generate the entire list upfront, you want an algorithm that given the current element, outputs the next one.
Also, if the order is not relevant, the problem becomes a little easier. To generate the next element in the lexicographic order requires possibly making several updates to the tuple that represents the next element; in the worst case you update all elements (imagine the transition from 01111 to 10000 for example). Instead, you can use a Gray code, which requires one or two updates at each step: Gray code - Wikipedia
Computing all n-tuples of a fixed set of elements is actually a really interesting problem. If you’re really serious about this, Knuth has a whole section about this problem called “Generating all Possibilities” in Volume 4A.
6 Likes
Also, if you’re only generating a tuple of indices, and the total number of combinations fits in a machine word, you can compute the tuple of indices using multiplication, division and modulo. It’s the same algorithm as converting an integer into a sequence of digits.
1 Like
Here's a parameter pack implementation I cooked up:
struct Product<each C: Collection>: IteratorProtocol, Sequence {
var collection: (repeat each C)
var index: (repeat (each C).Index)
var done: Bool
init(_ collection: repeat each C) {
self.collection = (repeat each collection)
self.index = (repeat (each collection).startIndex)
self.done = false
// We're immediately done if any collection is empty.
for (c, i) in repeat (each collection, each index) {
if (i == c.endIndex) {
done = true
}
}
}
mutating func next() -> (repeat (each C).Element)? {
if done { return nil }
defer {
// Advance the index by incrementing the first digit.
var carry = true
index = (repeat {
let c = each collection
var i = each index
// Increment this digit if necessary.
if carry {
c.formIndex(after: &i)
carry = false
}
// Check for wraparound.
if i < c.endIndex {
// Still in range.
return i
} else {
// We wrapped around; increment the next digit.
carry = true
return c.startIndex
}
}())
// If the last digit wrapped around, we're done.
done = carry
}
// Return the current element.
return (repeat (each collection)[each index])
}
}
for elt in Product(["a", "b", "c"], [0, 1, 2], [true, false]) {
print(elt)
}
This needs a Swift 6.0 compiler, because there the closure in next() captures pack element types.
I found one bug while working on this; adding a break after the done = true in init() causes a compiler crash.
8 Likes
Looks like you can avoid the crash by using Collection.isEmpty
for c in repeat each collection {
if c.isEmpty {
done = true
break
}
}
Interesting approach anyway!
3 Likes
Same implementation using Parameter Pack while requiring only Sequence
struct ProductX<each S: Sequence>: IteratorProtocol {
var sequence: (repeat each S)
var iterators: (repeat (each S).Iterator)
var nextValue: (repeat (each S).Element)?
init(_ sequence: repeat each S) {
self.sequence = (repeat each sequence)
self.iterators = (repeat (each sequence).makeIterator())
// We're immediately done if any collection is empty.
do {
let packed = try (repeat {
var i = each iterators
if let value = i.next() {
return (value, i)
} else {
throw CancellationError()
}
}())
self.iterators = (repeat {
let i = (each packed)
return i.1
}())
self.nextValue = (repeat {
let e = (each packed)
return e.0
}())
} catch {
self.nextValue = nil
}
}
mutating func next() -> (repeat (each S).Element)? {
guard let valueToReturn = self.nextValue else {
return nil
}
do {
var carry = true
let packed = try (repeat {
let s = each sequence
var i = each iterators
let previousValue = each valueToReturn
if carry {
carry = false
if let partValue = i.next() {
return (i, partValue)
} else {
carry = true
i = s.makeIterator()
if let partValue = i.next() {
return (i, partValue)
}
throw CancellationError()
}
}
return (i, previousValue)
}())
self.iterators = (repeat {
let i = (each packed)
return i.0
}())
self.nextValue = (repeat {
let e = (each packed)
return e.1
}())
if carry == true {
nextValue = nil
}
} catch {
nextValue = nil
}
return valueToReturn
}
}
This could be useful, if you want to make Product of none RandomAccessCollection. (Accessing Element of non RandomAccess Collection is slow operation)
1 Like
I converted it to a function.
`func product`
@inlinable public func product<each Collection: Swift.Collection>(
_ collection: repeat each Collection
) -> UnfoldSequence<
(repeat (each Collection).Element),
(collection: (repeat each Collection), index: (repeat (each Collection).Index))
> {
var done = false
for collection in repeat each collection {
guard !collection.isEmpty else {
done = true
break
}
}
return sequence(
state: (
collection: (repeat each collection),
index: (repeat (each collection).startIndex)
)
) { state in
if done { return nil }
defer {
// Advance the index by incrementing the first digit.
var carry = true
state.index = (repeat {
let collection = each state.collection
var index = each state.index
// Increment this digit if necessary.
if carry {
collection.formIndex(after: &index)
carry = false
}
// Check for wraparound.
if index < collection.endIndex {
// Still in range.
return index
} else {
// We wrapped around; increment the next digit.
carry = true
return collection.startIndex
}
}())
// If the last digit wrapped around, we're done.
done = carry
}
// Return the current element.
return (repeat (each state.collection)[each state.index])
}
}
Is it possible to return an opaque type?
With the above, you can actually use the result…
let sequence: some Sequence<(Int, Int)> = product([1], [2])
By changing the return type to
-> some Sequence<(repeat (each Collection).Element)>
…it compiles, but becomes not usable at all.
Return type of let 'sequence' requires the types 'Array.Element, Array.Element' and '(Int, Int)' be equivalent