python - 在python中求解(m选择x)= n的高效算法

鉴于
m:要设计的海报数量
n：可用颜色总数
解决
X：每张海报的颜色数量，以便每张海报具有唯一的颜色组合
服从方程式
（n选择x）=m
我已经用python编写了上述问题，源代码如下

factorial = []

def generateList(n):
    factorial.append(1)
    factorial.append(1)

    for i in range(2,n+1):
        factorial.append(i * factorial[i-1])

def calculateFac(n,i):
    return int((factorial[n]) / (factorial[i] * factorial[n-i]))

def ColorChoice(m,n):
    for i in range(1,int(n/2)+1):
        if m == calculateFac(n,i):
            return i
    return -1

def checkChoose(m,n):
    generateList(n)
    return ColorChoice(m,n)

print (checkChoose(35,7))

上面的解决方案只适用于小整数，但我需要一个解决方案来适用于较大的数字，例如当n=47129212243960时。
有什么有效的方法来解决这个问题吗？

最佳答案

因为(n choose x) == (n choose (n-x))，而且似乎您希望找到最小的x，所以我们可以在x和0之间搜索n/2此外，对于任意的n和m，可能不存在这样的x，但是可能你想要的是最小的这样的x，如果存在的话，<(n choose x) >= m，即最小的x保证你可以做m独特的颜色组合-用那个x你甚至可以做超过m独特的颜色组合。
这里有一个简单的o（n）解决方案，使用(n choose (x+1)) / (n choose x) == (n-x)/(x+1)这一事实，您可以通过按阶乘展开“choose”表达式，然后将其取消。

def x(m,n):
    n_choose_x = 1
    for x in xrange(1, n/2 + 1):
        n_choose_x = n_choose_x * (n+1-x) / x
        if n_choose_x >= m:
            return x
    return -1

print(x(70,8))
print(x(71,8))
print(x(57,8))
print(x(56,8))
print(x(55,8))
print("")
print(x(9999999, 47129212243960))
print(x(99999999471292122439609999999, 47129212243960))
print(x(99999999947129212243960999999471292122439609999999, 47129212243960))

这张照片：

4
-1
4
3
3

1
3
4

关于python - 在python中求解(m选择x)= n的高效算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33327319/