## 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.