Algorithms package: product(_:_) limited to two product terms only, for homogeneous element type, there should be one for any number of product terms?

Related Projects Algorithms
1

Algorithms package product(_:_:) supports product of a Sequence and a Collection, allow for heterogeneous element types. To do product of more than two terms, you have to call nested product(_:_:) and the result is in tuple, resulting in static code of fixed n-number of terms must be known in compile time.. This is fine when product terms element types are heterogeneous.

But for homogeneous element type for all product terms, there should be product(...) that can calculate product of any number of terms, allowing for dynamically handle any number of product terms.

This is what I come up with:

@inlinable
public func product<C: Collection>(_ terms: Array<C>) -> Array<Array<C.Element>> {
    switch terms.count {
    case 0:
        return []
    case 1:
        return terms[0].map { [$0] }
    default:
        var result = product(terms[0], terms[1]).map { [$0, $1] }
        for term in terms.dropFirst(2) {
            result = product(result, term).map { $0.0 + [$0.1] }
        }
        return result
    }
}


// Special case for Character:
public func product<C: Collection>(_ terms: Array<C>) -> [String] where C.Element == Character {
    switch terms.count {
    case 0:
        return []
    case 1:
        return terms[0].map { String($0) }
    default:
        var result = product(terms[0], terms[1]).map { String([$0, $1]) }
        for term in terms.dropFirst(2) {
            result = product(result, term).map { $0.0 + String($0.1) }
        }
        return result
    }
}

With this, we can do this:

let blah = product([[1,2,3], [4,5,6,7], [8,9,0]])
print(blah)

prints:

[[1, 4, 8], [1, 4, 9], [1, 4, 0], [1, 5, 8], [1, 5, 9], [1, 5, 0], [1, 6, 8], [1, 6, 9], [1, 6, 0], [1, 7, 8], [1, 7, 9], [1, 7, 0], [2, 4, 8], [2, 4, 9], [2, 4, 0], [2, 5, 8], [2, 5, 9], [2, 5, 0], [2, 6, 8], [2, 6, 9], [2, 6, 0], [2, 7, 8], [2, 7, 9], [2, 7, 0], [3, 4, 8], [3, 4, 9], [3, 4, 0], [3, 5, 8], [3, 5, 9], [3, 5, 0], [3, 6, 8], [3, 6, 9], [3, 6, 0], [3, 7, 8], [3, 7, 9], [3, 7, 0]]

I've not look in other algorithms if they are in similar situation.

1 Like
2

I think parameters packs might help with generating a heterogeneous product of an arbitrary dimension.

A legit use-case I'm running into for this is passing arguments to parameterized swift-testing tests. These tests only (AFAIK) accept two sequences. A workaround is to zip sequences… but this is not the same as a product across two sequences.

I suppose engineers to have the option to "roll their own" high-dimensional product function… but I do think there would be some impactful use-cases for shipping this (someday) in swift-algorithms.

1 Like
3

Almost got it (Godbolt):

struct ProductSequence<each Base: Sequence> {
    let base: (repeat each Base)

    init(_ base: repeat each Base) {
        self.base = (repeat each base)
    }
}

extension ProductSequence: Sequence {
    typealias Element = (repeat (each Base).Element)

    struct Iterator: IteratorProtocol {
        let base: (repeat each Base)
        var iterator: (repeat (each Base).Iterator)
        var element: Element?
        var started = false
        var complete = false

        init(_ product: ProductSequence) {
            self.base = product.base
            self.iterator = (repeat (each product.base).makeIterator())
        }

        mutating func next() -> Element? {
            func step<T: Sequence>(
                _ sequence: T, _ iterator: T.Iterator, _ element: T.Element?
            ) -> (iterator: T.Iterator, element: T.Element?) {
                if complete { return (iterator, element) }

                var i = iterator
                if let element = i.next() {
                    if started { complete = true }
                    return (i, element)
                }

                var reset = sequence.makeIterator()
                if let element = reset.next() {
                    return (reset, element)
                }

                return (reset, element)
            }

            complete = false

            let result: (repeat (iterator: (each Base).Iterator, element: (each Base).Element?))
            if element == nil {
                result = (repeat step(each base, each iterator, nil))
                started = true
                complete = true
            } else {
                result = (repeat step(each base, each iterator, each element!))
            }

            for case .none in repeat (each result).element {
                return nil
            }

            iterator = (repeat (each result).iterator)
            element = (repeat (each result).element!)

            if !complete { return nil }

            return element
        }
    }

    func makeIterator() -> Iterator {
        Iterator(self)
    }
}

It works fine with Strings and ClosedRanges

let product = ProductSequence("Swift", 3...4, 5...6)
for tuple in product {
    print(tuple)
}

but crashes badly with anything else.

1 Like
4

I think it's more like:

struct ProductSequence<Outer: Sequence, each Inner: Collection>

since Sequence types aren't guaranteed repeatable access.