7
\$\begingroup\$

I am trying to find number of integer partitions of given n - number. If I have n == 4, the answer should be 5 because:

  1. \$4 = 1+1+1+1\$
  2. \$4 = 2+1+1\$
  3. \$4 = 3+1\$
  4. \$4 = 2+2\$
  5. \$4 = 4\$

My code works properly but the matter is that it counts big numbers for a very long time. I have no idea how to optimize my code. Maybe you can help me to make it faster?

def get_answer(n):
    if n == 0:
        yield []
        return
    for p in get_answer(n-1):
        yield [1] + p
        if p and (len(p) < 2 or p[1] > p[0]):
            yield [p[0] + 1] + p[1:]
number_of_partitions=lambda n:sum(1 for _ in get_answer(n))
\$\endgroup\$
  • 1
    \$\begingroup\$ This will be of combinatorial complexity any way you do it - so I think we need a dynamic programming / memoization approach here. \$\endgroup\$ – Tamoghna Chowdhury Jul 30 '17 at 10:56
  • \$\begingroup\$ Use a concise generating function approach \$\endgroup\$ – hjpotter92 Jul 30 '17 at 12:47
  • \$\begingroup\$ @hjpotter92 I tried them all. Only accel_asc is a bit faster but it requires much more memory. That's why it will not do for me. \$\endgroup\$ – Nikita.K Jul 30 '17 at 14:41
  • \$\begingroup\$ @Nikita.K Are there any restrictions to what you can use? It seems like accel_asc is your best option in terms of speed. Otherwise, you're stuck with your funciton. In this case, I would first try a different implementation such as PyPy or maybe augment Python a bit with Cython. After that I would just use another language honestly. \$\endgroup\$ – Dair Jul 30 '17 at 23:11
  • \$\begingroup\$ @Dair Actually this task is from Codewars. So, I can't use any implementations. Also, Python is the only language I know. \$\endgroup\$ – Nikita.K Jul 31 '17 at 4:40
2
\$\begingroup\$

A slightly more efficient dynamic programming approach means you only need O(n) space:

def partitions(n):
    parts = [1]+[0]*n
    for t in range(1, n+1):
        for i, x in enumerate(range(t, n+1)):
            parts[x] += parts[i]
    return parts[n]

In []:
partitions(50)

Out[]:
204226

Note: this is trivial to extend to the coin change problem (the number of ways you can make change with certain coins: Ways to make change for a dollar), by restricted the values in the outer loop, e.g.:

def coin_change(n, coins):
    parts = [1]+[0]*n
    for c in coins:
        for i, x in enumerate(range(c, n+1)):
            parts[x] += parts[i]
    return parts[n]

In []:
coin_change(100, {1, 5, 10, 25, 50, 100})

Out[]:
293
\$\endgroup\$
1
\$\begingroup\$

My code works properly but the matter is that it counts big numbers for a very long time. I have no idea how to optimize my code. Maybe you can help me to make it faster?

...
number_of_partitions=lambda n:sum(1 for _ in get_answer(n))

Don't count. Calculate.

The Wikipedia article on partitions gives the Hardy-Ramanujan estimate \$P(n) = \Theta(n^{-1} e^{k \sqrt n})\$ with \$k=\pi \sqrt\frac23\$. Since your code finds the partitions to count them, and since the "average" partition has a lot of \$1\$s, your running time is \$\Omega(e^{k \sqrt n})\$.

The Wikipedia article also gives a number of recurrence relations, including one which uses generalised pentagonal numbers (giving a running time of \$\Theta(n^{1.5})\$), and another which uses the sum of divisors function (giving a running time of \$\Theta(n^2)\$ if you pre-calculate the sum of divisors using e.g. the sieve of Eratosphenes). An alternative quadratic approach (which you could find by following the Mathworld link from Wikipedia) uses the auxiliary function \$P(n,k)\$ for the number of partitions of \$n\$ into parts of which the largest is exactly \$k\$ and the recurrence \$P(n,k)=P(n-1,k-1)+P(n-k,k)\$.

\$\endgroup\$
0
\$\begingroup\$

This is a perfect task to solve with dynamic programming. Using a C++-script found here and some additional optimization, I created this script:

num = 100
scores = [[int(j==0 and i>0) for i in range(num)] for j in range(num)]
max_part = num-1
calculated = [1]

def get_combinations(n, x = max_part):
    for i in range(calculated[0], n+1):
        for j in range(1, x+1):
            if (i-j<0):
                scores[i][j] = scores[i][j-1]
                continue
            scores[i][j] = scores[i][j-1] + scores[i-j][j];
    calculated[0] = n
    return scores[n][x]

print(get_combinations(50))

This script outputs 204226, and additionally its output is identical for any input value (I only tested up to 65, because the function in your question ran slowly after that).

The major drawback of the dynamic solution is that it is space inefficient. To calculate get_combinations(n), one must use O(n^2) memory to store the scores-array. However, it performs much better for large values of n. And an additional feature (my addition to the C++-script) is that if you run the function multiple times, it doesn't recalculate any numbers.

Thus, if get_combinations(5) has been calculated, then a subsequent call to get_combinations(2) only requires an array lookup, and a subsequent call to get_combinations(10) is faster.

This function should work without issues for any n under 1000 (for input larger than 100 the variable num needs to be adjusted), and is 400 times faster for n = 65 on my machine in the worst case. Sequentially calculating all values between 1 and 1000 runs in <0.5s.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.