在swift中找到不重复计算的最佳组合方式

Question

我想为此类数学问题找到最佳 swift 解决方案：

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

虽然我知道组合公式

我使用这个 swift 阶乘函数：

func factorial(n: Int) -> Int {
    return n == 0 ? 1 : n * factorial(n — 1)
}

有没有办法建立一个函数，不只是通过替换上面公式中的变量来计算组合？

注意：

我认为这不是最优化的方式：

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

Answer 1

从 n 中选择 k 项的方法数由下式给出 binomial coefficient C(n, k)。 multiplicative formula 对于非负 n 和 k 可以在 Swift 中实现为

/// 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
}

这比使用阶乘的公式"better"

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

从某种意义上说，中间值不会变得那么大。（但它可以溢出，例如

C(70, 35) = 112186277816662845432

超出了64位整数的范围！）

示例 (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]

在您的特殊情况下，n 之间的握手次数人是 C(n, 2) = n*(n-1)/2。你可以用上面的方法计算功能或只是

func handshakes(n: Int) -> Int {
    return n*(n-1)/2
}

在swift中找到不重复计算的最佳组合方式

Find the best way for combination without repetition calculation in swift

math

factorial

swift