6

I need to create function which will take one argument int and output int which represents the number of distinct parts of input integer's partition. Namely,

input:3 -> output: 1 -> {1, 2}
input:6 -> output: 3 -> {1, 2, 3}, {2, 4}, {1, 5}
...

Since I am looking only for distinct parts, something like this is not allowed:

4 -> {1, 1, 1, 1} or {1, 1, 2}

So far I have managed to come up with some algorithms which would find every possible combination, but they are pretty slow and effective only until n=100 or so. And since I only need number of combinations not the combinations themselves Partition Function Q should solve the problem. Does anybody know how to implement this efficiently?

More information about the problem: OEIS, Partition Function Q

EDIT:

To avoid any confusion, the DarrylG answer also includes the trivial (single) partition, but this does not affect the quality of it in any way.

EDIT 2: The jodag (accepted answer) does not include trivial partition.

Improve this question
3
  • 1
    The link you provided gives a pretty clear set of function definitions for a memo-ized function to compute Q(n). Have you tried implementing that? Do you have some code to show us? Commented May 21, 2020 at 22:19
  • Unfortunately, I haven't achieved much, because I can't handle recursion properly especially s(n) part. So if you could give me a hint I will try to come up with something. Thanks Commented May 21, 2020 at 22:30
  • 1
    @kaktus_car--in my answer I implemented the approach in your Wolfram link and a simpler approach. The Wolfram was orders of magnitude faster than using a simple recurrence relation even with Memoization. Commented May 22, 2020 at 0:42

4 Answers 4

Reset to default
7

Tested two algorithms

  1. Simple recurrence relation

  2. WolframMathword algorithm (based upon Georgiadis, Kediaya, Sloane)

Both implemented with Memoization using LRUCache.

Results: WolframeMathword approach orders of magnitude faster.

1. Simple recurrence relation (with Memoization)

Reference

Code

@lru_cache(maxsize=None)
def p(n, d=0):
  if n:
    return sum(p(n-k, n-2*k+1) for k in range(1, n-d+1))
  else:
    return 1

Performance

n    Time (sec)
10   time elapsed: 0.0020
50   time elapsed: 0.5530
100  time elapsed: 8.7430
200  time elapsed: 168.5830

2. WolframMathword algorithm

(based upon Georgiadis, Kediaya, Sloane)

Reference

Code

# Implementation of q recurrence
# https://mathworld.wolfram.com/PartitionFunctionQ.html
class PartitionQ():
  def __init__(self, MAXN):
    self.MAXN = MAXN
    self.j_seq = self.calc_j_seq(MAXN)

  @lru_cache
  def q(self, n):
    " Q strict partition function "
    assert n < self.MAXN
    if n == 0:
      return 1

    sqrt_n = int(sqrt(n)) + 1
    temp = sum(((-1)**(k+1))*self.q(n-k*k) for k in range(1, sqrt_n))

    return 2*temp + self.s(n)

  def s(self, n):
    if n in self.j_seq:
      return (-1)**self.j_seq[n]
    else:
      return 0

  def calc_j_seq(self, MAX_N):
    """ Used to determine if n of form j*(3*j (+/-) 1) / 2 
        by creating a dictionary of n, j value pairs "
    result = {}
    j = 0
    valn = -1
    while valn <= MAX_N:
      jj = 3*j*j
      valp, valn = (jj - j)//2, (jj+j)//2
      result[valp] = j
      result[valn] = j
      j += 1

    return result

Performance

n    Time (sec)
10   time elapsed: 0.00087
50   time elapsed: 0.00059
100  time elapsed: 0.00125
200  time elapsed: 0.10933

Conclusion: This algorithm is orders of magnitude faster than the simple recurrence relationship

Algorithm

Reference

enter image description here

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Exactly what I wanted to achieve. Thank you for detail answer, comparisons, explanations. The Wolfram algorithm is just, wow, much faster than I thought it would be. Also after viewing your code I now better understand how the implementation of these algorithms looks like, which is important.
@kaktus_car--glad it was helpful. The tricky part was relating n to j, which I did by just enumerating j values and using the formula to see what n values they mapped onto a maintaining that in a dictionary.
Very helpful, because I've never encountered this type of problem and I did not know how to approach it. I learned much today. Yeah, and it was clever.
5

I think a straightforward and efficient way to solve this is to explicitly compute the coefficient of the generating function from the Wolfram PartitionsQ link in the original post.

This is a pretty illustrative example of how to construct generating functions and how they can be used to count solutions. To start, we recognize that the problem may be posed as follows:

Let m_1 + m_2 + ... + m_{n-1} = n where m_j = 0 or m_j = j for all j.

Q(n) is the number of solutions of the equation.

We can find Q(n) by constructing the following polynomial (i.e. the generating function)

(1 + x)(1 + x^2)(1 + x^3)...(1 + x^(n-1))

The number of solutions is the number of ways the terms combine to make x^n, i.e. the coefficient of x^n after expanding the polynomial. Therefore, we can solve the problem by simply performing the polynomial multiplication.

def Q(n):
    # Represent polynomial as a list of coefficients from x^0 to x^n.
    # G_0 = 1
    G = [int(g_pow == 0) for g_pow in range(n + 1)]
    for k in range(1, n):
        # G_k = G_{k-1} * (1 + x^k)
        # This is equivalent to adding G shifted to the right by k to G
        # Ignore powers greater than n since we don't need them.
        G = [G[g_pow] if g_pow - k < 0 else G[g_pow] + G[g_pow - k] for g_pow in range(n + 1)]
    return G[n]

Timing (average of 1000 iterations)

import time
print("n    Time (sec)")
for n in [10, 50, 100, 200, 300, 500, 1000]:
    t0 = time.time()
    for i in range(1000):
        Q(n)
    elapsed = time.time() - t0
    print('%-5d%.08f'%(n, elapsed / 1000))

n    Time (sec)
10   0.00001000
50   0.00017500
100  0.00062900
200  0.00231200
300  0.00561900
500  0.01681900
1000 0.06701700
Improve this answer

4 Comments

First, sorry for the late response and thank you for your answer. Now, this is definitely a great approach. It is faster than the currently accepted one and your solution is not recursive so it won't raise the Recursion error which happens with the mentioned solution when n >= 250 . As far as I see I should accept your answer, of course if there are arguments against, I am more than open for discussion.
I believe this is the best solution of all, can you give clues on how was this derived?
I can see now this is from the recursive realtionship here: archive.lib.msu.edu/crcmath/math/math/p/p121.htm it finds the rest of coefficients, knowing only the first coefficient which is 1
@IlyaAhmed The explanation is in the answer. If there's a particular part of the setup or solution that you don't understand then please elaborate. This is a basic generating function problem. The generating function is a polynomial, the coefficient of x^(n-1) is the number of solutions. We just perform the polynomial multiplication for each term to get the coefficients of the polynomial, truncating to only terms with order less than x^n.
1

You can memoize the recurrences in equations 8, 9, and 10 in the mathematica article you linked for a quadratic in N runtime.

Improve this answer

1 Comment

Good suggestion, I agree it is the best approach.
1 
def partQ(n):

    result = []

    def rec(part, tgt, allowed):
        if tgt == 0:
            result.append(sorted(part))
        elif tgt > 0:
            for i in allowed:
                rec(part + [i], tgt - i, allowed - set(range(1, i + 1)))

    rec([], n, set(range(1, n)))

    return result

The work is done by the rec internal function, which takes:

  • part - a list of parts whose sum is always equal to or less than the target n
  • tgt - the remaining partial sum that needs to be added to the sum of part to get to n
  • allowed - a set of number still allowed to be used in the full partitioning

When tgt = 0 is passed, that meant the sum of part if n, and the part is added to the result list. If tgt is still positive, each of the allowed numbers is attempted as an extension of part, in a recursive call.

Improve this answer

3 Comments

Thanks for the answer and explanation, the code works but it is not what I need. I want to get only the number of combinations, or regarding your answer len(result) without computing them (or if it is possible to compute them fast), so the answer for large n would be very quick. Any suggestions how to achieve that?
@amital, You've got some small bugs. you need to handle tgt == 1, and the initial call should have set(range(1, n+1))
@RobNeuhaus - Regarding the >1 issue - corrected the code (although I suspect it does not matter). Regarding the range(1, n + 1) suggestion, I think that would be incorrect, since it will include the trivial partition, which the output samples do not include.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.