Finding all combinations in an array (Swift 5) with enumeration

Question

I have some code in C# that does exactly what I like to do: Enumerate all combinations of a given length in an array (with repetitions). Like so:

public static IEnumerable<IEnumerable<int>> CombinationsWithRepition(IEnumerable<int> input, int length)
{
    if (length <= 0)
        yield return new List<int>();
    else
    {
        foreach (int i in input)
            foreach (IEnumerable<int> c in CombinationsWithRepition(input, length - 1))
            {
                List<int> list = new List<int>();
                list.Add(i);
                list.AddRange(c);
                yield return list;
            }
    }
}

Usage:

foreach (var c in CombinationsWithRepition(new int[] { 0, 1, 2 }, 2))
{
    foreach (var x in c)
        Console.Write(x + " : ");

    Console.WriteLine("");
}

Output:

0 : 0
0 : 1
0 : 2
1 : 0
1 : 1
1 : 2
2 : 0
2 : 1
2 : 2

Now I want to port that to swift 5, but I failed. I searched the web but I can only find solutions without repetition or solutions that creates a huge array. It is important to have the ability to enumerate the whole thing (no output as an array or a list containing all results). I don't know how to port "yield" to swift code.

This is the closest I have found: How do I return a sequence in Swift?

Thank you in advance

Answer 1

In languages that have yield, it is a call back to the calling function returning a result. The state of the current function is maintained and continues when the yield returns.

We can implement something like that in Swift with a closure callback.

This is a nearly direct translation of your routine:

func combinationsWithRepetition(_ input: [Int], length: Int, yield: ([Int]) -> ()) {
    if length <= 0 {
        yield([])
    }
    else {
        for i in input {
            combinationsWithRepetition(input, length: length - 1) { c in
                var list = [Int]()
                list.append(i)
                list += c
                yield(list)
            }
        }
    }
}

combinationsWithRepetition([0, 1, 2], length: 2) { c in
    print(c.map(String.init).joined(separator: " : "))
}

Output:

0 : 0
0 : 1
0 : 2
1 : 0
1 : 1
1 : 2
2 : 0
2 : 1
2 : 2

---

There are times when the caller wants to control the function that is yielding. If you'd like to be able to stop the function, you can have the yield callback return a Bool telling the yielding function if it should continue.

Consider this example:

// Generate squares until told to stop
func squares(_ yield: (_ n: Int) -> Bool) {
    var i = 1
    var run = true
    while run {
        run = yield(i * i)
        i += 1
    }
}

// print squares until they exceed 200
squares() { n -> Bool in
    print(n)
    return n < 200
}

1
4
9
16
25
36
49
64
81
100
121
144
169
196
225

Answer 2

Swift does not have a yield statement. In order to enumerate all combinations “lazily” (without storing all combinations in an array) we have to implement a Sequence whose Iterator computes the combinations on demand in its next() method.

Here is a possible implementation. The idea is to maintain an array of “positions” as state variable. Initially it is

 [ base.startIndex, ..., base.startIndex ]

where base is the collection (e.g. Array) from which the combinations are build. In each iteration, the last position is incremented. If it reaches base.endIndex then it is reset to base.startIndex, and the next position is incremented. (This is exactly how you would increment a number in a number system, e.g. a decimal number.) If the first position has been incremented up to base.endIndex then the enumeration is done.

In each iteration, this positions array is mapped to the corresponding array of elements from the base collection and returned from the next() method.

Only this array and two boolean variables are needed as intermediate storage. The implementation uses ideas from this answer on Code Review, such as having only a single exit point in the next() method.

struct CombinationsWithRepetition<C: Collection> : Sequence {

    let base: C
    let length: Int

    init(of base: C, length: Int) {
        self.base = base
        self.length = length
    }

    struct Iterator : IteratorProtocol {
        let base: C

        var firstIteration = true
        var finished: Bool
        var positions: [C.Index]

        init(of base: C, length: Int) {
            self.base = base
            finished = base.isEmpty
            positions = Array(repeating: base.startIndex, count: length)
        }

        mutating func next() -> [C.Element]? {
            if firstIteration {
                firstIteration = false
            } else {
                // Update indices for next combination.
                finished = true
                for i in positions.indices.reversed() {
                    base.formIndex(after: &positions[i])
                    if positions[i] != base.endIndex {
                        finished = false
                        break
                    } else {
                        positions[i] = base.startIndex
                    }
                }

            }
            return finished ? nil : positions.map { base[$0] }
        }
    }

    func makeIterator() -> Iterator {
        return Iterator(of: base, length: length)
    }
}

Example 1:

let comb = CombinationsWithRepetition(of: [0, 1, 3], length: 2)
for c in comb { print(c) }

Output:

[0, 0]
[0, 1]
[0, 3]
[1, 0]
[1, 1]
[1, 3]
[3, 0]
[3, 1]
[3, 3]

Example 2:

let comb = CombinationsWithRepetition(of: "abcd", length: 3)
for c in comb { print(c) }

Output:

["a", "a", "a"]
["a", "a", "b"]
["a", "a", "c"]
["a", "a", "d"]
["a", "b", "a"]
...
["d", "d", "c"]
["d", "d", "d"]

Answer 3

The following seems to achieve what you wanted:

let source = Array((0...5))
let length = 3

func combinationsWithRepetition(input source: [Int], length: Int) -> [[Int]] {
  if length == 0 { return [[]] }
  let baseArray = combinationsWithRepetition(input: source, length: length - 1)
  var newArray = [[Int]]()
  for value in source {
    baseArray.forEach {
      newArray.append($0 + [value])
    }
  }
  return newArray
}

print(combinationsWithRepetition(input: [0, 1, 2], length: 2))
// [[0, 0], [1, 0], [2, 0], [0, 1], [1, 1], [2, 1], [0, 2], [1, 2], [2, 2]]

Or to be more functional:

func combinationsWithRepetition(input source: [Int], length: Int) -> [[Int]] {
  if length == 0 { return [[]] }
  let baseArray = combinationsWithRepetition(input: source, length: length - 1)
  return baseArray.flatMap { array in
    return source.map { array + [$0] }
  }
}

Basically, combinationsWithRepetition returns an array of all possible arrays of a combination of length elements. For instance, combinationsWithRepetition(input: [0, 1, 2, 3], length: 1) returns [[0], [1], [2], [3]]. length of more than 0 are handled using a recursion, which your originally seems to use (probably, since I don't know C# syntax). Swift supports array addition, e.g., [1] + [2] is [1, 2], and the above code is doing that for all values from source to the elements (which are possible combinations of length length - 1) of the resulting array.

The second code uses flatMap which "flattens" a nested array into an array, e.g. [[[1, 2], [1, 3]], [[1, 4], [1, 5]]] into [[1, 2], [1, 3], [1, 4], [1, 5]]. Otherwise the logic is exactly identical with the one using an iteration.

To get the output as in your post, you can do:

combinationsWithRepetition(input: [0, 1, 2], length: 2).forEach {
  print($0.map(String.init).joined(separator: " : "))
}

which results in

0 : 0
0 : 1
0 : 2
1 : 0
1 : 1
1 : 2
2 : 0
2 : 1
2 : 2