### re: Another Way to Find Max Partitions VIEW POST

re: Awesome thinking! Thanks for the algorithm! I'm on my phone so hard to time, so I'll let you try it, but a couple of ideas that might make the cod...

Amazing! Thanks for making the code more Pythonic! But, won't the if in the list comprehension be computed k times? In my version, it was computed just once, but then the del made O(k) shifts, so both seem nevertheless sort of balanced. I don't know precisely why, but after I benchmarked your code with mine, my code still ran in a quarter of time taken by your code.

Yes indeed, I just got my hands on a computer and I tested everything out, you were faster than me :)
I have a very slight increase in performance with this version :

from math import ceil # no dynamic lookup of ceil

def summands_opt(n):
k = ceil(((1 + 8*n)**0.5 - 1) / 2)  # one affectation less
the_sum = k * (k+1) // 2 # no casting, python will make an int
summands = list(range(1, k+1))
del summands[the_sum-n-1]
return summands


The del statement does not fail when there is nothing to delete.

Awesome! Now this is some production-quality code! Thanks for adding readability to the code as well.

Don't listen to this tired programmer who did too much Ocaml lately: the condition is necessary because of how python interprets negative indices.
I tried other versions, thinking that using more iterators should be faster, but surprisingly no. Here are all the codes and timings I did:

import math
from math import ceil # no dynamic lookup of ceil
from itertools import chain

def summands(n):
k = ((1 + 8*n)**0.5 - 1) / 2
k = math.ceil(k)
summands = list(range(1, k+1))
the_sum = int(k * (k+1) / 2)
if the_sum - n > 0:  # If n is not senior.
del summands[the_sum-n-1]
return summands

def summands_opt(n):
k = ceil(((1 + 8*n)**0.5 - 1) / 2)
the_sum = k * (k+1) // 2
summands = list(range(1, k+1))
if the_sum - n > 0:  # If n is not senior.
del summands[the_sum-n-1]
return summands

def summands_iter(n):
k = ceil(((1 + 8*n)**0.5 - 1) / 2)
the_sum = k * (k+1) // 2
pluck = max(0, the_sum - n)
return list(chain(
range(1, pluck),
range(pluck+1, k+1)))

def summands_list(n):
k = ceil(((1 + 8*n)**0.5 - 1) / 2)
the_sum = k * (k+1) // 2
pluck = max(0, the_sum - n)
return list(range(1, pluck)) + list(range(pluck+1, k+1)

>>> from timeit import timeit
>>> timeit(setup='from partition import summands', stmt='summands(10000)', number=100000)
0.17959438299976682
>>> timeit(setup='from partition import summands_opt', stmt='summands_opt(10000)', number=100000)
0.15117240200015658
>>> timeit(setup='from partition import summands_iter', stmt='summands_iter(10000)', number=100000)
0.2742825210002593
>>> timeit(setup='from partition import summands_list', stmt='summands_list(10000)', number=100000)
0.23539557200001582


The last two surprised me a lot: how can the chaining of iterators be slower than concatenation of lists? But unsurprisingly the definition of a custom generator to chain was even slower…

def summands_gen(n):
k = ceil(((1 + 8*n)**0.5 - 1) / 2)
the_sum = k * (k+1) // 2
pluck = max(0, the_sum - n)
def gen():
yield from range(1, pluck)
yield from range(pluck+1, k+1)
return list(gen())


However, once removing the casting to list, summands_iter would be the only version that do not cause an overflow for very large numbers :

def summands_iter(n):
k = ceil(((1 + 8*n)**0.5 - 1) / 2)
the_sum = k * (k+1) // 2
pluck = max(0, the_sum - n)
return chain(
range(1, pluck),
range(pluck+1, k+1))

>>> summands_opt(2**60)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/home/christophe/python/partition.py", line 17, in summands_opt
summands = list(range(1, k+1))
MemoryError
>>> for i in summands_iter(2**60): print(i)
# still printing !


Whoa! That was some deep analysis!

Code of Conduct Report abuse