subsum_partitioner.py

'''Minimal example demonstrating that code still runs even if variable names are terrible.'''

import itertools
import random

def swippy_swap(set1, set2, item1, item2):
    a = set1.copy()
    a.discard(item1)
    a.add(item2)
    b = set2.copy()
    b.discard(item2)
    b.add(item1)
    return a, b

def cost(set1, set2):
    return abs(sum(set1)-sum(set2))

def swippy_swappy_search(set1, set2):
    minn = cost(set1, set2)
    minns = (set1, set2)
    changed = False
    for item1 in set1:
        for item2 in set2:
            foo, bar = swippy_swap(set1, set2, item1, item2)
            if cost(foo, bar) < minn:
                minn = cost(foo, bar)
                minns = (foo, bar)
                changed = True
    return minns, changed, minn

def repeated_swippy_swappy_search(set1, set2):
    while True:
        (set1, set2), changed, minn = swippy_swappy_search(set1, set2)
        if not changed:
            return (set1, set2), minn

def global_search(set1, set2):
    '''Take all equal size half subsets lol'''
    mega_set = set1 | set2
    minn = cost(set1, set2)
    minns = (set1, set2)
    for items in itertools.combinations(mega_set, len(mega_set)//2):
        sitems = set(items)
        rosco = cost(sitems, mega_set - sitems)
        if rosco < minn:
            minn = rosco
            minns = (sitems, mega_set - sitems)
    return minns, minn
        
nels = 4
crunchy = 0
for _ in range(1000000):
    foo = {random.randint(1, 9) for _ in range(nels)}
    bar = {random.randint(1, 9) for _ in range(nels)}
    if len(foo) != nels:
        continue
    if len(bar) != nels:
        continue 
    if len(foo|bar) != 2*nels:
        continue
    crunchy += 1
    sets, minn = repeated_swippy_swappy_search(foo, bar)
    gsets, gminn = global_search(foo, bar)
    if minn != gminn:
        print(sets, minn, gsets, gminn)
print(crunchy)