Refactor the code which performs "cross-product", "reduce", "product of list" and "sum of list"

Question

I have come up with a sequence of steps to find the maximum product of y positive numbers which add up to x. But the program is highly inefficient.

Here's my code:

from itertools import product
from functools import reduce
from operator import mul

for i in range(int(input())):               # <-- number of pairs of input
    lgr = 1
    k = set()
    x, y = tuple(map(int, input().split())) #  <-- the input pairs
    p = product(range(1, x+1), repeat=y)    #  <-- gets the cross product
    for i in p:
        if sum(i) == x:                     #  <-- checks if sum is equal to x
            k.add(i)                        #  <-- adds it to a set() to remove duplicates
    for i in k:
        tmp = reduce(mul, i, 1)             #  <-- multiplies the items in the tuple to get the largest
        if tmp > lgr:
            lgr = tmp
    print(lgr)

But say for an input like 14 7 it just takes too long (around 20s). Is there a better way to do it?

Update 1: I've managed to improve a bit by using combinations_with_replacement and set & list comprehension... but I believe it can be done better... any suggestions...?

from itertools import combinations_with_replacement
from functools import reduce
from operator import mul

for i in range(int(input())):
    lgr = 1
    x, y = tuple(map(int, input().split()))
    k = {i for i in combinations_with_replacement(range(1, x+1), y) if sum(i) == x}
    lgr = max([max(reduce(mul, i, 1), lgr) for i in k])
    print(lgr)

Answer 1

The comments contain two proofs that a better solution exists.

1. Start with an array of all ones, then repeatedly add one to the smallest number (because that gives the largest percentual increase) until you reach the maximum allowed sum. This can be fomulated as a proof by induction. – Rainer P.

   This can be proven rather simply by using Python, but it can also be proven with a basic formula. If we start with the array \$y, y-1\$ and we have to increase one of the values by one then we can deduce adding one to the \$y-1\$ value results in a larger product.

   $$ yy \gt (y + 1)(y-1)\\ y^2 \gt y^2 - 1\\ $$

   This change works regardless of what the rest of the array is. And so we know adding one to the lowest value always nets the biggest increase.
   I used to not be very good with math, and so a more hands on proof using Python may be easier to follow and agree with.

   import math
   
   
   def inc_1(numbers, pos):
       nums = numbers[:]
       nums[pos] += 1
       return nums
   
   
   def proof(total, amount):
       if total < amount:
           return 0
       numbers = [1] * amount
       for i in range(total - amount):
           d = i % amount
           if d:
               larger = math.prod(inc_1(numbers, d - 1))
               smaller = math.prod(inc_1(numbers, d))
               if smaller < larger:
                   raise ValueError('proof does not hold')
           numbers[d] += 1
       return numbers, math.prod(numbers)
   
   
   print(proof(14, 7))
   print(proof(302, 5))
   

2. if the product contains two factors which differ by more than one, then it is not optimal: Say these are \$x\$ and \$y\$ with \$x < y\$, then replace them by \$x + 1\$ and \$y - 1\$. Now \$(x+1)(y-1) = xy + (y - x - 1) > xy\$. – Carsten S

   ^{Changed to use mathjax}

   With this description the factors are the array of numbers. With this we can start with a random assortment of numbers that total the desired number, and we can continuously improve the product.

   $$ 3, 8\\ 3 < 8\\ 4 \times 7 \gt 3 \times 8\\ 28 \gt 24\\ 5 \times 6 \gt 4 \times 7\\ 30 \gt 24 $$

---

In all the fastest solution is to just use divmod, and produce the product once.

def maximum_product_with_sum(total, count):
    q, r = divmod(total, count)
    return (q+1)**r * q**(count-r)


print(maximum_product_with_sum(14, 7))
print(maximum_product_with_sum(302, 5))

Answer 2

One immediate improvement is realizing that for e.g the input 14 7, all combinations like x x x x x x 9 and above can never sum to 14, because even for the minimal case x = 1, 9 + 6*1 = 15. So you can vastly reduce the number of combinations you need to check by using

k = {i for i in combinations_with_replacement(range(1, x - y + 2), y) if sum(i) == x}

For the input 14 7 this constitutes a difference of 77520 possible combinations down to 3432.

This adds a constraint only on the last number, but you could take this to its logical extreme and write code that always aborts the combinations once the sum has been reached.

One other thing you should do is use better names and use functions. I have no idea that k is a list of combinations of numbers, or what this means. Also, using i (and j, k, n, too, for that matter) for anything other than an integer is not helpful either.

I would at least rewrite your code to this:

from itertools import combinations_with_replacement
try:  # Python 3.8+
    from math import prod
except ImportError:
    from functools import reduce
    from operator import mul
    def prod(x):
        """Returns the product of all elements of `x`, similar to `sum`."""
        return reduce(mul, x, 1)

def maximum_product_with_sum(x, n):
    """Return the maximum product of all `n` positive numbers that sum to `x`."""
    r = range(1, x - n + 2)
    candidates = {candidate 
                  for candidate in combinations_with_replacement(r, n)
                  if sum(candidate) == x}
    return max(map(prod, candidates), default=1)

if __name__ == "__main__":
    for _ in range(int(input())):
        x, n = tuple(map(int, input().split()))
        print(maximum_product_with_sum(x, n))

Note that I also added some short docstrings to describe what each function does and simplified getting the maximum, your inner call to max was not needed. The optional keyword argument argument default of max is the default value if the iterable is empty.

I also added a if __name__ == "__main__": guard to allow importing from this script from another script without the code being run.

Here is the performance measured against your second function (the first one is way too slow) once for the input x 7 and once for 14 n:

You can see that this code is not only faster in general, it also becomes much faster if n > x / 2.

Answer 3

Thanks @Graipher & @Peilonrayz for taking time to answer my question. Yesterday around 7PM I discussed this with my brilliant friend Abhay, who gave me a clue on how this can be solved with just \$O(n)\$ complexity.

To keep the question in mind:

Find the maximum product of y positive numbers which adds up to x.

This is how he explained it to me:

If we observe the pattern of tuples that qualify for the output, we can easily see that all the values lie closer to \$\frac{x}{y}\$. See for the pairs:

| Pairs    | Solution Tuple                                | Max Product |
|----------|-----------------------------------------------|-------------|
| (14, 7)  | (2, 2, 2, 2, 2, 2, 2)                         | 128         |
| (20, 15) | (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2) | 32          |
| (13, 4)  | (3, 3, 3, 4)                                  | 108         |
| (5, 3)   | (1, 2, 2)                                     | 4           |

If we take a even closer look we find that those values in the tuple are either ceil(\$\frac{x}{y}\$) or floor(\$\frac{x}{y}\$). And the last individual element is what is left off in sum.

Hence the program according to him was:

from math import floor, ceil

for t in range(int(input()):
    x, y = map(int, input().split())
    psum, product = 0, 1
    for i in range(y):
        if i == y-1: product *= x - psum
        else:
            num = x/y
            num1, num2 = floor(num), ceil(num)
            psums, product = (psum+num1, product*num1) if abs(num - num1) < abs(num - num2) else (psum+num2, product*num2)
    print(product)

@RBarryYoung's comment came close but I think x's and y's got messed up... (please correct me if it is not so).

I've never seen how well this answer fares @Peilonrayz's solution, but I would love to get some insight on it.