pedrouan - 1 year ago 142
Swift Question

# Find the best way for combination without repetition calculation in swift

I'd like to find best swift solution for this kind of mathematic question:

Assume having 5 people in the room. Everybody have to shake hands to
each other. How many combinations does it bring?

While I know the combination formula

and I use this swift factorial func:

``````func factorial(n: Int) -> Int {
return n == 0 ? 1 : n * factorial(nāāā1)
}
``````

Is there a way to establish a function, that counts combinations not by only replacing variables in the above formula?

NOTE:

I don't think this is the most optimised way:

``````let combinations = factorial(n: 5)/(factorial(n: 2)*factorial(n: 3)) // 10
``````

The number of ways to choose `k` elements from `n` is given by the binomial coefficient `C(n, k)`. The multiplicative formula for nonnegative `n` and `k` can be implemented in Swift as

``````/// Binimomial coefficient C(n, k) for non-negative integers n, k.
func binomial(n: Int, _ k: Int) -> Int {
precondition(k >= 0 && n >= 0)
if (k > n) { return 0 }
var result = 1
for i in 0 ..< min(k, n-k) {
result = (result * (n - i))/(i + 1)
}
return result
}
``````

This is "better" than the formula

``````C(n, k) = n! / (k! * (n-k)!)
``````

in the sense that the intermediate values do not become larger than the final result.

Example (Pascal's triangle):

``````for n in 0...5 {
print((0...n).map { k in binomial(n, k) })
}

// Output:
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]
``````

In your special case, the number of handshakes between `n` persons is `C(n, 2) = n*(n-1)/2`. You can compute that with above function or just with

``````func handshakes(n: Int) -> Int {
return n*(n-1)/2
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download