求解的高效算法 (m choose x) = n in python

Question

给定

m: number of posters to design
n: total number of available colors

求解

x: number of colors for each poster so that each poster has a unique combination of colors

以方程为准

(n choose 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.

有什么有效的方法可以解决这个问题吗？

Answer 1

因为(n choose x) == (n choose (n-x))，你好像想找最小的x，我们可以在0和n/2之间搜索x。此外，对于任意 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))

这会打印：

求解的高效算法 (m choose x) = n in python

Efficient algorithm to solve (m choose x) = n in python

python

algorithm

permutation