grouping_problem

grouping_problem.py

# A group of N integer numbers need to be divided fairly into K subgroups. 
# A fair division is that the max of the sums of K subgroups is minimal

def grouping(n, k):
    a = sum(n) / k
    nums = sorted(n, reverse=True)
    groups = []
    gsums = []

    for _ in range(k):
        group = [nums.pop(0)]
        groups.append(group)
        gsum = group[0]

        while True:
            gnext_num = 0
            gnext_i = -1
            for i, num in enumerate(nums):
                if gsum + num <= a and num > gnext_num:
                    gnext_num = num
                    gnext_i = i

            if gnext_i > -1:
                gsum += gnext_num
                group.append(gnext_num)
                nums.pop(gnext_i)
            else:
                break

        gsums.append(gsum)

    for num in nums:
        i = gsums.index(min(gsums))
        groups[i].append(num)
        gsums[i] += num

    return groups

if __name__ == "__main__":
    import random

    print(grouping([12, 11, 10, 9, 8, 7, 3, 2], 4))
    print(grouping([6, 6, 5, 2, 1, 1], 2))
    print(grouping([6, 6, 5, 2, 1, 1], 3))
    print(grouping([6, 6, 5, 2, 1, 1], 4))
    print(grouping([9, 2, 1], 2))
    print(grouping([6, 5, 3, 2, 2], 2))
    print(grouping([8, 5, 5, 2, 2, 6], 5))

    for i in range(100):
        n = random.sample(range(1,100), 7)
        print('N =', n)
        for k in range(2, 5):
            result = grouping(n, k)
            print('    K =', k, ": ", result, 'Avg:', sum(n) / k, 'Max: ', max([sum(g) for g in result]))