This type of combination/permutation is missing. What is it called?

Related Projects Algorithms
9

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.

12 Likes