Match list elements from two lists that sum to the same amount

Question

I have two lists of numbers (A and B), and some combination of elements in A should sum to the same total as some combination of elements in B. As groups are matched, the matched elements would be removed from their lists to continue until all combinations are matched.

For example, with the two lists:

A = [7, 8, 12, 300, 350]
B = [3, 4, 20, 150, 500]

The combined sum totals of the matched groups would be:

{7: [{'A': [7], 'B': [3, 4]}],
 20: [{'A': [8, 12], 'B': [20]}],
 650: [{'A': [300, 350], 'B': [150, 500]}]}

The naive way I've addressed this so far is to get the sum of all possible combinations from each list (pow(2, len(mylist))-1), do a set intersection between the two sets of all combinations, and remove elements sequentially until all elements are accounted for.

Does anyone know of a more efficient algorithm to accomplish this? Expanding to all possible combinations for each list to then do a set intersection can get large.

Here's the naive way:

def getCombos(stuff):
    res = []
    for L in range(1, len(stuff) + 1):
        for subset in itertools.combinations(stuff, L):
            res.append(subset)
    return res

Acombo = getCombos(A)
Bcombo = getCombos(B)
AcomboSum = [sum(tup) for tup in Acombo]
BcomboSum = [sum(tup) for tup in Bcombo]

sumint = sorted(set(AcomboSum).intersection(set(BcomboSum)))

Arem = [a for a in A]
Brem = [b for b in B]

d = collections.defaultdict(list)

for s in sumint:
    idx = sumint.index(s)
    Avals = Acombo[AcomboSum.index(s)]
    Bvals = Bcombo[BcomboSum.index(s)]

    if set(Avals).issubset(set(Arem)) and set(Bvals).issubset(set(Brem)):
        d[s].append([Avals, Bvals])
        for v in Avals: Arem.pop(Arem.index(v))
        for v in Bvals: Brem.pop(Brem.index(v))
    else:
        continue

print(d)

Can you post your naive solution so we can see what you've tried? — user3483203, May 10 '18 at 17:08
Are the inputs such that the solution is guaranteed to be contiguous slices of the sorted arrays, or that was just in the example? — jdehesa, May 10 '18 at 17:13
Also, I suppose the goal is to make the largest possible number of matches? Otherwise, assuming both arrays sum the same amount, you could just match them complete. — jdehesa, May 10 '18 at 17:21
Do you have to find the single set of combinations which ensures all numbers from both lists are consumed? Is it possible that you could find a set of matches which exhausts list B, but leave some numbers unmatched in list A or vice versa? The problem seems severely underspecified. Or is this covered by "until all combinations are matched" as a "combination" seems to include a single number as in match of 7 from A with {3,4} from B? — kdopen, May 10 '18 at 17:47
@jdehesa - no they won't be contiguous slices, it can occur anywhere. Yes, the plan is to make the most granular matches (most number of matches) — wc001, May 10 '18 at 18:31
Downgrading to a comment: if elements of A and B are positive, negating B and taking union with A leads to a well-known [subset sum problem](https://en.wikipedia.org/wiki/Subset_sum_problem). — hilberts_drinking_problem, May 11 '18 at 07:09
related: [How to divide a set into two subsets such that difference between the sum of numbers in two sets is minimal?](https://stackoverflow.com/q/6597180/4279). In Russian: [Как делить входной список целых чисел на два списка с одинаковыми суммами элементов?](https://ru.stackoverflow.com/q/587750/23044) — jfs, May 24 '18 at 20:15

webmite · Answer 1 · 2018-05-10T18:18:43.847

1

Sort both arrays in reverse descending order.

Then calculate all sums in array A and Sort that in reverse descending order.

if A[n] represents all elements in array A

and B[m] represents all elements in array B

and sum_A[n!] represents all possible sums of elements in A.

and sum_A.sorted(reverse=True) represents that array sorted in descending order.

create a new array B_start[n!] and store the index i of the first element in B that is smaller than the sum_A[i].

Now for any sum_A[i] element you only have to consider elements in B from B[ B_start[i] ] to B[m] for combinations of sums

Note: this only works if all numbers in the arrays are positive.

edited May 10 '18 at 18:18

answered May 10 '18 at 18:10

webmite

575
3
6

Just found [this](https://math.stackexchange.com/questions/89419/algorithm-wanted-enumerate-all-subsets-of-a-set-in-order-of-increasing-sums) method that generates subsets in order of element sums. It takes time complexity from O(n 2^n) to O(2^n). This is optimal since A=B case needs O(2^n) space. – hilberts_drinking_problem May 11 '18 at 06:04

Match list elements from two lists that sum to the same amount

1 Answers1