Balance two lists till their sums are equal & with min swaps within the two lists in Python

Question

a = [70, 30, 33, 23, 4, 4, 34, 95]
b = [50, 10, 10, 7]

I've tried this, but i know this is not accurate enough

if sum(a) > sum(b):
   a.sort()
   b.sort()
   temp = [int(i) for i in a]
   i=0
   while(sum(b) <= sum(temp)  and (i <= len(a) - 1)):
      b.append(a[i])
      temp.remove(a[i])
      i = i+1

    a = [int(i) for i in temp]
if sum(b) > sum(a):
    a.sort()
    b.sort()
    temp = [int(i) for i in b]
    i=0
    while(sum(a) <= sum(temp)  and (i <= len(b) - 1)):
        a.append(b[i])
        temp.remove(b[i])
        i = i+1        

    b = [int(i) for i in temp]

Result was:

sums = 186, 184

lists = [7, 10, 70, 95, 4], [4, 10, 23, 30, 33, 34, 50]

Required Answer :

sums = 185, 185

lists = [7, 10, 23, 50, 95], [4, 4, 10, 30, 33, 34, 70]

What do you mean with additions? Does a swap counts as one? This looks like something for *dynamic programming*. — Willem Van Onsem, Jul 23 '17 at 12:01
@DavidGladson will the lists always provide an acceptable solution? Or could it happen that they cannot be balanced? — EsotericVoid, Jul 23 '17 at 12:13
@Bit Firstly, I'm trying to figure out for the ones which can be balanced. Yeah for the ones which cannot be balanced, we need to obtain the min possible difference between their sums. — David Gladson, Jul 23 '17 at 12:16
This is a special case of linear integer programming. You could perhaps use one of the solvers mentioned [here](https://stackoverflow.com/questions/26305704/python-mixed-integer-linear-programming). — Gribouillis, Jul 23 '17 at 12:42
@DavidGladson Could you please share the source where you found this problem? It's a nice challenge, if it's from a coding website and there's more of this I would like to see more! — EsotericVoid, Jul 23 '17 at 12:46

Jonas Adler · Answer 1 · 2017-07-23T13:00:50.780

The problem you are trying to solve is called the subset sum problem and is NP complete, so you are not going to get much better than brute force search.

This at least gives a solution using brute force:

from itertools import chain, combinations

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def lst_difference(lst, other):
    s = list(lst)
    for el in other:
        s.remove(el)
    return s

a = [70, 30, 33, 23, 4, 4, 34, 95]
b = [50, 10, 10, 7]

lst = a + b
total = sum(lst)

for subset in powerset(lst):
    if sum(subset) == total // 2:
        other_subset = lst_difference(lst, subset)

        print('subset1 = {}, subset2 = {}'.format(subset, other_subset))

Which gives these solutions:

subset1 = (70, 95, 10, 10), subset2 = [30, 33, 23, 4, 4, 34, 50, 7]
subset1 = (30, 95, 50, 10), subset2 = [70, 33, 23, 4, 4, 34, 10, 7]
subset1 = (30, 95, 50, 10), subset2 = [70, 33, 23, 4, 4, 34, 10, 7]
subset1 = (33, 23, 34, 95), subset2 = [70, 30, 4, 4, 50, 10, 10, 7]
subset1 = (33, 95, 50, 7), subset2 = [70, 30, 23, 4, 4, 34, 10, 10]
subset1 = (30, 33, 23, 4, 95), subset2 = [70, 4, 34, 50, 10, 10, 7]
subset1 = (30, 33, 23, 4, 95), subset2 = [70, 4, 34, 50, 10, 10, 7]
subset1 = (23, 95, 50, 10, 7), subset2 = [70, 30, 33, 4, 4, 34, 10]
subset1 = (23, 95, 50, 10, 7), subset2 = [70, 30, 33, 4, 4, 34, 10]
subset1 = (70, 23, 4, 4, 34, 50), subset2 = [30, 33, 95, 10, 10, 7]
subset1 = (30, 33, 95, 10, 10, 7), subset2 = [70, 23, 4, 4, 34, 50]
subset1 = (70, 30, 33, 4, 4, 34, 10), subset2 = [23, 95, 50, 10, 7]
subset1 = (70, 30, 33, 4, 4, 34, 10), subset2 = [23, 95, 50, 10, 7]
subset1 = (70, 4, 34, 50, 10, 10, 7), subset2 = [30, 33, 23, 4, 95]
subset1 = (70, 4, 34, 50, 10, 10, 7), subset2 = [30, 33, 23, 4, 95]
subset1 = (70, 30, 23, 4, 4, 34, 10, 10), subset2 = [33, 95, 50, 7]
subset1 = (70, 30, 4, 4, 50, 10, 10, 7), subset2 = [33, 23, 34, 95]
subset1 = (70, 33, 23, 4, 4, 34, 10, 7), subset2 = [30, 95, 50, 10]
subset1 = (70, 33, 23, 4, 4, 34, 10, 7), subset2 = [30, 95, 50, 10]
subset1 = (30, 33, 23, 4, 4, 34, 50, 7), subset2 = [70, 95, 10, 10]

OP said that each list can reach size of 100 though, plus you need to find the solution with minimal swaps. — EsotericVoid, Jul 23 '17 at 12:51
The problem is NP complete. Hes not going to get significantly faster than this. — Jonas Adler, Jul 23 '17 at 12:58

score 0 · Answer 2 · answered Jul 23 '17 at 12:23

0

Some numbers need to move from a to b, and some numbers need to move from b to a. The set of numbers that move is a subset of the set of all numbers from both lists. In your example, there are only 12 numbers, which means 2**12 == 4096 subsets. As it is a small number, a brute force approach should succeed.

answered Jul 23 '17 at 12:23

Gribouillis

2,230
1
9
14

yeah true, but the maximum possible size of each list is 100 :( – David Gladson Jul 23 '17 at 12:25
All right, forget about the brute force approach :) – Gribouillis Jul 23 '17 at 12:26

score 0 · Answer 3 · answered Jul 23 '17 at 14:48

Well, here's my take on this. As the others said, this problem cannot be solved in polynomial time, so this gets significantly slow when each list needs to give multiple items to the other. Anyway, here is the code:

from itertools import combinations
from collections import Counter

a = [70, 30, 33, 23, 4, 4, 34, 95]
b = [50, 10, 10, 7]

def balance(small, big):
    small.sort()
    big.sort()
    diff = sum(big) - sum(small)
    if diff < 0:
        small, big = big, small
    stack = {(0, 1)}  # each element is (# of elements to take from small, # of elements to take from big)
    while stack:
        i, j = sorted(stack, key=lambda t: t[0]+t[1]).pop(0)
        stack.remove((i, j))
        diff = sum(big) - sum(small)
        if i is 0:
            matches = [(Counter(), Counter(x)) for x in combinations(big, j) if diff - 2 * sum(x) is 0]
        else:
            matches = [(Counter(x), Counter(y)) for x in combinations(small, i) for y in combinations(big, j) if
                       diff - 2 * sum(y) + 2 * sum(x) is 0]
        if matches:
            return list((Counter(small) - matches[0][0] + matches[0][1]).elements()), \
                   list((Counter(big) - matches[0][1] + matches[0][0]).elements())
        else:
            if sum(big[-j:]) * 2 - sum(small[-i:]) > diff and i + 1 < len(small):
                stack.add((i + 1, j))
            if sum(big[:j]) * 2 - sum(small[:i]) < diff and j + 1 < len(big):
                stack.add((i, j + 1))

balance(a, b) returns ([7, 10, 50, 23, 95], [4, 4, 30, 33, 34, 70, 10])

Balance two lists till their sums are equal & with min swaps within the two lists in Python

I've tried this, but i know this is not accurate enough

Required Answer :

3 Answers3