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.