algorithm - 计算 $2n$ 元素可以配对多少种方式的更快方法？

Question

所以问题在于 2n 元素有多少种配对方式，我的方法是将所有奇数相乘小于 2n。

(2n-1)*(2n-3)*...*1

但我的教授声称在算法意义上可以更快地完成，但我真的不知道这样做的方法。有什么提示吗？谢谢!

Answer 1

更新:这可能不是您要问的:

您的问题改写为:从一组 2n 个元素中选择两个元素有多少种方法？也称为组合，二项式系数或选择数，阅读 "n choose k" .

您可以采用公式 n!/(k! * (n - k)!)，将n替换为2n，然后代数化简为(2n - 1) * n:

#!/usr/bin/env python
# coding: utf-8

def pairs(n):
    return (2 * n - 1) * n

# there is only one pair for an 2n element set {0, 1}
print(pairs(1)) # prints 1

# pairs of {0, 1, 2, 3} = {0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}, {2, 3}
print(pairs(2)) # prints 6