1

Given

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

solve for

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

subject to the equation

(n choose x) = m

I have coded the above problem in python and the source code is given below

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))

The above solution will only work for small integers but I need a solution to work for larger numbers, e.g. when n = 47129212243960.

Is there any efficient way to solve this?

Amit Kumar Gupta
  • 17,184
  • 7
  • 46
  • 64
James92
  • 81
  • 2
  • 8
  • if you can do with an approximation of factorial (and don't need the exact value) you could use [stirling's approximation](https://en.wikipedia.org/wiki/Stirling's_approximation). – hiro protagonist Oct 25 '15 at 07:52
  • 3
    (n choose x) is 0, 1 or at least n, so if n is 47129212243960 then you'll have at least 47 trillion posters to design. Is there a mistake in your question, or is this just a theoretical puzzle? – Paul Hankin Oct 25 '15 at 07:54
  • You should be using `//` integer division. Also, there's an efficient factorial function in the math module. However, your loop would be faster just calculating the (n choose r) sequence directly rather than doing it via factorials (either calculated each time with `math.factorial` or using values stored in a list). – PM 2Ring Oct 25 '15 at 08:00
  • 1
    Also, your `ColorChoice` function will fail to find an `i` if it doesn't get an exact match. Is that what you really want? If not, consider changing that `==` to a `>=`. – PM 2Ring Oct 25 '15 at 08:02
  • Similar question was asked [here](http://stackoverflow.com/questions/4775029/finding-combinatorial-of-large-numbers). Has some ideas. – trincot Oct 25 '15 at 08:03
  • @trincot: That question's related, but James92 wants to solve for `x` in the equation `m=(n choose x)`, rather than merely calculating `(n choose x)` for large `n` and `x`. – PM 2Ring Oct 25 '15 at 08:13
  • How big is the `m` you expect to go with that `n = 47129212243960`? When `n` is that large `m` rapidly becomes _huge_ for even modest `x`, as Paul Hankin mentioned earlier. – PM 2Ring Oct 25 '15 at 08:15
  • @PaulHankin Sorry my mistake , Please forgive me . M value is 47129212243960 – James92 Oct 25 '15 at 08:34

1 Answers1

2

Since (n choose x) == (n choose (n-x)), and it seems like you want to find the minimal x, we can search for x between 0 and n/2. Also, for arbitrary n and m, it's possible no such x exists, but probably what you want is the minimal such x, if one exists, such that (n choose x) >= m, i.e. the smallest x guaranteeing you can make m unique colour combinations -- with that x you may even be able to make more than m unique colour combinations.

There's a simple O(n) solution, using the fact that (n choose (x+1)) / (n choose x) == (n-x)/(x+1), which you can see by expanding the "choose" expressions in terms of factorials, and cancelling things out.

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))

This prints:

4
-1
4
3
3

1
3
4
Amit Kumar Gupta
  • 17,184
  • 7
  • 46
  • 64