food_partition.py

from heapq import nsmallest, nlargest
from itertools import product


def findSmallestStd(food, n):
    food.sort(reverse=True)
    while len(food) % n:
        food.append(0)
    family_count = len(food) // n

    if n == 2:
        # optimal
        return list(zip(food[:len(food)//2], reversed(food[len(food)//2:])))
    else:
        # heuristic approach
        partition = [[] for _ in range(family_count)]

        for food_item in sorted(food, reverse=True):
            partition.sort(key=lambda f: sum(f) if len(f) < n else float('inf'))
            partition[0].append(food_item)

        return local_search(partition, calc_std(partition))


def local_search(partition, best_std, N = 20):
    # find indices with smallest and largest sum
    families1 = nsmallest(N, partition, key=sum)
    families2 = nlargest(N, partition, key=sum)
    best_improved_swap = None

    for family1, family2 in product(families1, families2):
        for index1, index2 in product(range(len(family1)), range(len(family2))):
            family1[index1], family2[index2] = family2[index2], family1[index1]
            std = calc_std(partition)
            if std < best_std:
                best_std = std
                best_improved_swap = (family1, family2, index1, index2)
            family1[index1], family2[index2] = family2[index2], family1[index1]

    if best_improved_swap:
        family1, family2, index1, index2 = best_improved_swap
        family1[index1], family2[index2] = family2[index2], family1[index1]
        partition = local_search(partition, best_std)
    elif N < 100:
        return local_search(partition, best_std, 100)
    return partition


def calc_std(partition):
    sums = [sum(f) for f in partition]
    mean = sum(sums) / len(partition)
    return (sum((f - mean)**2 for f in sums) / len(partition))**0.5


if __name__ == "__main__":
    with open('codegolfvectoroptimization.txt') as f:
        v = [int(line.strip()) for line in f]
        results = []
        for n in [2, 3, 23]:
            food_partition = findSmallestStd(v[:], n)
            std = calc_std(food_partition)
            results.append(std)
            print('STD for n = {0}: {1}'.format(n, std))
            print(food_partition)
        print('{0} = {1}'.format(' + '.join(map(str,results)), sum(results)))