swiftmathfactorial

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

enter image description here

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

Solution

  • The number of ways to choose k items 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

    /// Binomial 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 using factorials

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

    in the sense that the intermediate values do not become so large. (But it can overflow, for example

    C(70, 35) = 112186277816662845432
    

    exceeds the range of 64-bit integers!)

    Example (Pascal's triangle):

    for n in 0...7 {
        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
    }