High execution time on number partitioning program in Python 2.7

Question

I am writing a program to count only the partitions of a number with distinct parts. I am using a bottom-up approach to dynamic programming to generate partition lists from previously obtained partition lists. I think my program runs correctly, as I have tested for some inputs and verified from OEIS. But it's extremely slow for n>15. I think my algorithm has a complexity currently north of O(n^3), but I couldn't think of a better way to do it. Can anyone help with making it faster?

# Logic - The partition of a number 'n', will be 1 + the partition of 'n-1', 2 + the partition of 'n-2', and so on. # So we start from 1, and build partition lists based on previously gotten partitions # The loop doesn't have to go all the way till 1. # For example, for 6, we only have to go till 'n-3' and stop, because after that, we only get duplicate lists. This is not to say that we don't get # duplicates before, but after 'n-3', we get JUST duplicates # So we only have to go till n-x >= x from collections import Counter compare = lambda x, y: Counter(x) == Counter(y) def make_partitions(n): # Bottom up approach starts at 1 and goes till n, building on partitions already obtained # partitions dictionary contains list of lists of partitions # Ex - 1: [[1]] # Ex - 2: [[2], [1,1]] # Ex - 3: [[3], [2,1], [1,1,1]] partitions = {} start = 1 while start <= n: partitions[start] = [] # Appending the number itself as a partition of length 1 partitions[start].append([start]) # prev stores the number currently being used to build the partition list prev = start - 1 # pp stores all partition lists obtained so far for the current number pp = [] while prev >= start-prev: # curr_partitions stores the partition lists that make up the desired number, FROM the current number # Ex - for desired number 6, in first loop, it stores those lists which make up 6 from those of 5; in the second loop, from those of 4 and so on curr_partitions = [] prev_partitions = partitions[prev] for p in prev_partitions: q = list(p) q.append(start-prev) # self-explanatory. compare function is used to see if the list already exists does_exist_already = False for ppp in pp: if compare(q, ppp): does_exist_already = True if not does_exist_already: curr_partitions.append(q) # We have got the entire list of partitions that make up the desired number FROM the current number, so we add to the dictionary partitions[start].extend(curr_partitions) prev -= 1 pp.extend(curr_partitions) start += 1 return partitions def answer(n): partitions = make_partitions(n) req_partition_list = partitions[n] final_partition_list = [] count = 0 # This for loop is to weed out lists which contain duplicate values for p in req_partition_list: c = Counter(p) if all(v==1 for v in c.values()): final_partition_list.append(p) count += 1 return count if __name__ == '__main__': n = int(raw_input()) print answer(n) 

Answer 1

Indentation

Your code is indented using a mixture of spaces and newlines. In Python, the use of 4 spaces per indent level is preferred. While Python 2 allows for mixed indentation, PEP8 recommends these be converted to spaces exclusively. Your indentation format seems to have affected display of the following lines:

 partitions[start].extend(curr_partitions) prev -= 1 pp.extend(curr_partitions) start += 1 return partitions 

The resulting code does not run. I have cleaned up indentation for make_partitions:

from collections import Counter compare = lambda x, y: Counter(x) == Counter(y) def mp(n): partitions = {} curr_partitions = [] start = 1 while start <= n: partitions[start] = [] partitions[start].append([start]) prev = start - 1 pp = [] while prev >= start-prev: curr_partitions = [] prev_partitions = partitions[prev] for p in prev_partitions: q = list(p) q.append(start-prev) does_exist_already = False for ppp in pp: if compare(q, ppp): does_exist_already = True if not does_exist_already: curr_partitions.append(q) partitions[start].extend(curr_partitions) prev -= 1 pp.extend(curr_partitions) start += 1 return partitions 

Partitions

The edited code produces the following output for n = 7:

{1: [[1]], 2: [[2], [1, 1]], 3: [[3], [1, 1, 1]], 4: [[4], [1, 1, 1, 1],[1, 1, 2]], 5: [[5], [1, 1, 2, 1]], 6: [[6], [1, 1, 2, 1, 1], [1, 1, 2, 2], [1, 1, 1, 3 ]], 7: [[7], [1, 1, 1, 3, 1], [1, 1, 2, 1, 2], [1, 1, 2, 3]]} 

It seems that partitions containing integers in the range n/2 < i < n are not included. Then, it is hard to see how final_partition_list could contain the correct partitions. And, checking small values of n:

n = 3, output = 1

n = 4, output = 1

n = 5, output = 1

n = 6, output = 1

etc.

Your code may not necessarily be broken, but simply a victim of incorrect conversion from mixed indentation to spaces only.

Answer 2

Here are a few improvements:

partitions[start] = [] # Appending the number itself as a partition of length 1 partitions[start].append([start]) 

Can be more succinctly written as:

partitions[start] = [[start]] 

You should compute start - prev once and reuse it:

while 2*prev >= start: curr_partitions = [] prev_partitions = partitions[prev] diff = start - prev for p in prev_partitions: p.append(diff) 

Note that p should already be a list.

Your duplicate finding can be improved by breaking once a hit has been found:

does_exist_already = False for ppp in pp: if compare(p, ppp): does_exist_already = True break if not does_exist_already: curr_partitions.append(p) 

Or, even better, use the short circuit evaluation of any:

if not any(compare(p, ppp) for ppp in pp): curr_partitions.append(p) 

The weeding out of lists with duplicates can be sped-up using a set instead of collections.Counter:

for p in req_partition_list: if len(p) == len(set(p)): final_partition_list.append(p) count += 1 

Finally, some stylistic remarks. Python has an official style-guide, PEP8, which programmers are encouraged to adhere to.

It recommends using a space before and after operators. It also encourages using easy to understand names for variables. p, pp, ppp and q are not easy to understand.