list_partitions.py

# "given an array of integers and a number n, partition the array into
# n pieces so that their sums are as equal as possible"

import itertools
import numpy as np
import sys

def powerset(input:list) -> list:
    # returns a list of tuple lists of all of the permutations of elements
    # [1,2,3] -> [[(1, 2, 3)], [(1,), (2, 3)], [(1,), (2,), (3,)], [(1,), (3,), (2,)],
    #   [(2,), (1, 3)], [(2,), (1,), (3,)], [(2,), (3,), (1,)], [(3,), (1, 2)],
    #   [(3,), (1,), (2,)], [(3,), (2,), (1,)], [(1, 2), (3,)], [(1, 3), (2,)],
    #   [(2, 3), (1,)]]
    #TODO make this return combinations, not permutations
    set_combinations = []
    
    set_combinations.append([tuple(input)])
    for n in range(1, len(input)):
        for combination_set in itertools.combinations(input, n):
            for recursive_set in powerset(list(set(input).difference(set(combination_set)))):
                #print("checking recursive set", recursive_set)
                set_combinations.append([combination_set, *recursive_set])
    return set_combinations

def minimum_partitions(input:list, n:int) -> tuple:
    # create powerset of the input list and only check sums of permutations of length n
    minimum_partition, minimum_sum = None, sys.maxsize
    for combination in powerset(input):
        if len(combination) != n:
            continue
        sums =  [sum(c) for c in combination]
        mean = np.mean(sums)
        diff = sum([abs(mean - combination_sum) for combination_sum in sums])
        if diff < minimum_sum:
            minimum_sum = diff
            minimum_partition = combination
    return minimum_partition

if __name__ == '__main__':
    input = [1,2,3]
    #print(powerset([1,2,3]))
    x = minimum_partitions(input, 2)
    print(x)
    print("-------")

    print(minimum_partitions([1,2,3,4], 2))
    print("-------")
    print(minimum_partitions([1,2,3,4], 3))
    # 
    # [1,2,3,4], 3
    #print(x)

$ python list_combination.py 
[(3,), (1, 2)]
-------
[(1, 4), (2, 3)]
-------
[(3,), (4,), (1, 2)]