Dividing list into subsets

[deanhystad]

This is the recursive solution with a cache. It makes 376 guesses and computes 61 partial solutions for a bag of 20 numbers divided into 5 groups.

import random

## Save partial solutions to speed things up.
solutions = {}

def sticks(bag, count):
    '''Split bag into count groups.  Find the grouping that results
    in the highest minimum group score.  Group score is the sum of
    numbers in the group.
    '''

    sticks.guesses += 1
    # This is a recursive solution with a cache.
    # Reuse partial solution when possible
    if score := solutions.get((len(bag), count)):
        return score

    if count == 1:
        # This is the last group and end of recursion.
        # Return the group score
        score = (sum(bag), [bag])
        solutions[(len(bag), count)] = score
        return score

    # Find the best grouping for the remaining groups.
    # Split the bag into two groups with the size of the
    # first group ranging from 1 to len(bag)-count+1.
    # Use recursing to find the best grouping for the
    # second part.
    best_score = 0
    for i in range(1, len(bag)-count+1):
        score, groups = sticks(bag[i:], count-1)
        groups = [bag[:i]] + groups
        score = min(score, sum(bag[:i]))

        if score > best_score:
            best_score = score
            best = groups

    solutions[(len(bag), count)] = (best_score, best)
    return (best_score, best)

sticks.guesses = 0
bag = random.choices(range(1, 101), k=20)
score, groups = sticks(bag, 5)
print('Groups', groups)
print('Score', score, [sum(group) for group in groups])
print('Guesses', sticks.guesses, 'Solutions', len(solutions))

I tried the same experiment with a bag of 50 numbers and 10 groups. This code makde 6,601 guesses, cached 376 partial solutions and ran in a little under a second. I disabled the cache and it made 2,054,455,634 and ran for an hour. The non-recursive solution I posted earlier solved it in a few milliseconds and one time only needed 7 guesses.