Algorithm Of The Day : Combinatory

So, I'd like to take x elements out of an array of n elements. I know from statistical analysis that there are a precise number of combinations:

But what are they? There are a few classic algorithms to do that, but most of them are recursive and use an accumulator, not exactly Swift's forte, especially if you don't know the right keyword. Cue inout

So here's the rough idea: every time we select an item in the array, we have only n-1 items to pick from, and x-1 items to pick. So it's recursive in nature. But we have an array, which means that we can make every possible combinations using the first item in the array first, then start again by removing the first item, and we should never repeat the combinations.

Here's an example: let's take 3 elements out of an array of 4

John Paul Ringo George

----------------------

John Paul Ringo
John Paul       George
John      Ringo George
     Paul Ringo George

It definitely looks like loops: We do all of John's first, then when we're done we do Paul's, and then we're done because we don't have enough people to start with Ringo.

Another way of looking at it is "I've selected John, now start again with the rest of the list and pick 2", then "I've selected Paul, now start again with the rest of the list and pick 1", then "I've started with Ringo, now start again with the rest of the list and pick 1". When we're done with the lists starting with John, we remove him, start with Paul, and there's only one choice.

In swift, because of the extension mechanism, it's easy to generalize to every array, but we still need that recursion that needs both where we are and what's left to work. Then all we need to manage is the special edge cases:

• there is no element in the array (because it's easy to deal with)
• there is less elements in the array than we want (ditto)
• there is exactly as many elements in the array as we want (well duh, there's only one possibility)

So here is the algorithm, with accumulators passed with inout (to modify them in the callee and the caller):

extension Array { // combinatory
    fileprivate func recArrangements(len: Int, start: Int, cur: inout [Element], result : inout [[Element]]) {
        if len == 0 {
            result.append([Element](cur))
        } else {
            var i = start
            while i <= (self.count-len) {
                cur[cur.count - len] = self[i]
                recArrangements(len: len-1, start: i+1, cur: &cur, result: &result)
                i += 1
            }
        }
    }
    
    func arrangements(of number: Int) -> [[Element]]? {
        if self.count == 0 { return nil }
        else if number > self.count { return nil }
        else if number == self.count { return [self] }
        var buffer = [Element](repeating: self[0], count: number)
        var result = [[Element]]()
        recArrangements(len: number, start: 0, cur: &buffer, result: &result)
        return result
    }
}

Proofs that it works:

> ["John", "Paul", "Ringo", "George"].arrangements(of: 3)
$R0: [[String]]? = 4 values {
  [0] = 3 values {
    [0] = "John"
    [1] = "Paul"
    [2] = "Ringo"
  }
  [1] = 3 values {
    [0] = "John"
    [1] = "Paul"
    [2] = "George"
  }
  [2] = 3 values {
    [0] = "John"
    [1] = "Ringo"
    [2] = "George"
  }
  [3] = 3 values {
    [0] = "Paul"
    [1] = "Ringo"
    [2] = "George"
  }
}

["Potassium",
"Calcium",
"Scandium",
"Titanium",
"Vanadium",
"Chromium",
"Manganese",
"Iron",
"Cobalt",
"Nickel",
"Copper",
"Zinc",
"Gallium",
"Germanium",
"Arsenic",
"Selenium",
"Bromine",
"Krypton"].arrangements(of: 3).count
$R1: Int? = 43758

Which fits $$\frac{18!}{8!.10!}=43758$$

Unfortunately, as with most recursive algorithms, its complexity is fairly horrendous... It is equivalent to 3 nested for loops (the way to write that code is left as an exercise), which means a whopping n³... Then again, combinatory has a way of being exponential anyways. I wonder if there is a way to be more efficient.