Find the min and max with one term being a sum of an nCr combination of the array and the other term the sum of the remaining items

Question

Say you are given an array of signed integers called NUMBERS of length r. Say NUMBERS is equal to

1, 2, 3, 4, 5

where r = 5.

 

You want to form a sum X of any n elements of the set NUMBERS and multiply this by the sum Y of the remaining m elements for any given n. So the length of the NUMBERS array is (n + m) words in memory.

This sum is of the form:

(x1 +x2 +x3 +...+xn)*(y1 +y2 +...+ym)

 

For example, with n = 2 you could have a possible combination for X be the sum of the arbitrary n = 2 elements 1 and 4, and thus the sum Y of the remaining m = 3 elements be 2 + 3 + 5. You then multiply both sums to get: X * Y = 5 * 10 = 50.

 

---

Formally:

Given (n + m) signed integers, we want to minimize and maximize the result of the algebraic expression of the form:

(x1 +x2 +x3 +...+xn)*(y1 +y2 +...+ym)

for a fixed given n.

---

 

This involves finding all nCr combinations of the set NUMBERS where n is given, and then finding the sum X for each combination, then calculating the sum Y of the remaining elements not used for the sum X. Then multiplying both. Using the combinatorics nCr formula you can obtain the number of possible combinations the sum X and the corresponding sum Y, and then brute force every single multiplication to see which will yield the smallest or largest result.

I am not sure how to proceed, especially since recursion and nested for loops are outside the scope of this first project.

Answer 1

I added a comment but deleted it as I realised I did a mistake. However, I have done some more experiments. I add it as an answer to be able to use formatting.

I haven't done extensive experiments, so I do not guarantee it holds true in all situations but the tests I have made shows that, if you sort the set of numbers, then this fact seems to hold true (when n<=m):

minval = (sum of first item(s) * sum of [remaining] last item(s))
maxval = (sum of first item(s) + last item(s)) * (sum of [remaining] middle item(s))

For example, if you get the set A{4, 8, 1, 6, 3} => A{1, 3, 4, 6, 8} and n=2, then:

minval = (A[0] + A[1]) * (A[2] + A[3] + A[4]) = 72
maxval = (A[0] + A[4]) * (A[1] + A[2] + A[3]) = 135

For my experiments I used set lengths from len = 4 to len = 8. These experiments show that the above seems to hold true all the time for these set lengths, and with variations of n from n=2 to n=(set.length-2) (for n=1 (and n=(set.length-1)) the answer is obvious). For set.length=3 seems to be slightly different but consistent every time with this combos give min and max values.

Since it holds true for set lengths 4 to 8, I assume this is the case for set lengths larger than 8 too.

Set length of 3 is kind of "edge cases" but still consistent if sorted with (or it is not directly an edge case, but the fact that n>m):

minval = A[1] * (A[2]) * A[3]
maxval = (A[1] + A[2]) * A[3]

Set lengths of 1 and 2 (if existing) are simple cases.

Hence, if the above always holds true, you only need to sort the list and then calculate the min and max value as per above which simplifies things a lot I guess.

EDIT: After or before sorting, you can calculate the sum of the set. Then you only need to do:

x1 = (A[0] + A[1])
x2 = (A[0] + A[4])
minval = x1 * (totalsum - x1) = 72
maxval = x2 * (totalsum - x2) = 135

EDIT2: After further experiments, it looks like the above does not hold true in all cases as outlined above but there is a pattern for sure that I am sure you can take advantage of.