Find the maximum number of combinations from a data set

Question

I need to write a function that finds the maximum number of combinations from a data set, where the sum of each of the subset combinations are >= a target value. Once numbers are taken from the data_set and put into a combination they cannot be reused in another combination For example data_set = [1,2,3,4,5,6,7,8,9,10] target_value = 5 the combinations would be 1: [10] 2: [9] 3: [8] 4: [7] 5: [6] 6: [5] 7: [4,1] 8: [3,2] an example of bad grouping would be 1: [1,2,3] 2: [4,5] 3: [6] 4: [7] 5: [8] 6: [9] or 1: [1,2,3] 2: [4,5] 3: [6,7,8,9]. I believe a constraint to be the number of subsets cannot be greater than sum(data_set)/target_value i.e. data_set = [5,5,5,5,5] target_value = 5 yields [5],[5],[5],[5],[5].

For context I have a large set of items I need to buy from a store, the store gives a coupon every time your purchase is over $150, if you buy everything at once you receive one coupon but if you split your items into small purchases as close to $150 as possible you will receive the maximum coupons possible.

This is the current code but it is obviously not optimized I'm having trouble scanning ahead for better matches

from numpy import random


def get_groups(item_list=[], target=0):
    groups = []

    def recurse(current_group, remaining_item_list):
        for index in range(len(remaining_item_list)):
            if sum(current_group) + remaining_item_list[index] < target:
                current_group.append(remaining_item_list[index])
                if index+1 == len(remaining_item_list):
                groups.append(current_group)
            else:
                current_group.append(remaining_item_list[index])
                groups.append(current_group)
                recurse([], remaining_item_list[index+1:])
                break

    item_list.sort(reverse=True)
    recurse([], item_list)

    return groups

items = [ random.randint(50) for i in range(21)]
target = 150

groups = get_groups(items, target)

print("Items: {}".format(items))

for index, group in enumerate(groups, start=1):
print("Group {}: {}, total: {}, length: {}".format(index, group, sum(group), len(group)))

EDIT: here is some much more optimized code I am sure it is not 100% correct but its better

from numpy import random


def get_groups(item_list=[], target=0):
    groups = []

    def recurse(current_group, remaining_item_list):
        for index in range(len(remaining_item_list)):
            remaining_item_list.sort(reverse=True)
            if sum(current_group) + remaining_item_list[index] < target:
                current_group.append(remaining_item_list[index])
                if index+1 == len(remaining_item_list):
                    groups.append(current_group)
            elif sum(current_group) + remaining_item_list[index] > target and current_group:
                reverse_search(current_group, remaining_item_list)
                remaining_item_list.sort(reverse=True)
                recurse([], remaining_item_list[index:])
                break
            else:
                current_group.append(remaining_item_list[index])
                groups.append(current_group)
                recurse([], remaining_item_list[index+1:])
                break
    
    def reverse_search(current_group, remaining_item_list):
        for index in range(len(remaining_item_list)):
            remaining_item_list.sort()
            if sum(current_group) + remaining_item_list[index] < target:
                current_group.append(remaining_item_list.pop(index))
                if index+1 == len(remaining_item_list):
                    groups.append(current_group)
            else:
                current_group.append(remaining_item_list.pop(index))
                groups.append(current_group)
                current_group = []
                break


    recurse([], item_list)

    return groups

items = [ random.randint(50) for i in range(20)]
target = 150

items.sort(reverse=True)

print("Items: {}".format(items))

groups = get_groups(items, target)

for index, group in enumerate(groups, start=1):
    print("Group {}: {}, total: {}, length: {}".format(index, group, sum(group), len(group)))```

Answer 1

The following approach does not guarantee an optimal solution but it will produce one in almost all cases.

The main function starts by determining the maximum number of groups that can be formed and builds the groups by adding the largest item value that fits within the target boundary. This will produce groups that only exceed the target value by a portion of their smallest item. If the last group formed reaches the target value, then, all preceding groups also reach it and there is no additional optimization needed. If the last group does not reach the target, then an optimization function is called to swap items between groups to spread some of the extras down to the last group(s).

from bisect import bisect_right
from itertools import combinations

def bonusGroups(numbers,target):
    numbers  = sorted(numbers)
    nbGroups = sum(numbers)//target
    if not nbGroups: return [numbers]
    groups   = [[] for _ in range(nbGroups)]
    
    # build initial groups
    for ig,g in enumerate(groups[:-1]):
        gap = target - sum(g)
        while numbers and gap > 0:
            i = max(0,bisect_right(numbers,gap) - 1)
            g.append(numbers.pop(i))
            gap -= g[-1]
        while g and min(g) <= target-sum(g):
            i = g.index(min(g))
            groups[ig+1].append(g.pop(i))
    groups[-1].extend(numbers)

    # last group reaches target, no spreading required
    if sum(groups[-1]) >= target:
        return groups

    return spreadGroups([*filter(None,groups)],target)

The optimization function will try to remove items from the first groups and replace them with items of subsequent groups (starting from last). The items are selected and matched up in a way that increase the subsequent group's sum without making the first group go below the target. To keep this efficient, the logic starts by removing as few items as possible and increases the removal combination size progressively until the new spread makes all groups reach the target (or removal size exceeds the largest group's size):

def spreadGroups(groups,target):
    groups.sort(key=sum,reverse=True)
    spreading = True
    remSize   = 1
    while spreading and any(sum(g) < target for g in groups):
        spreading = False
        for ig,g in enumerate(groups[:-1]):
            if remSize >= len(g): continue
            extra   = sum(g)-target
            if not extra: continue
            remSums = { sum(g[i] for i in idx):idx
                        for idx in combinations(range(len(g)),remSize) }
            for subSum,indexes in remSums.items():
                for tg in groups[-1:ig:-1]:
                    idx = matchSum(tg,max(0,subSum-extra),subSum-1)
                    if not idx and subSum>extra: continue
                    g.extend(tg.pop(i) for i in sorted(idx,reverse=True))
                    tg.extend(g.pop(i) for i in sorted(indexes,reverse=True))
                    if remSize>1: ig,remSize = -1,1
                    groups[ig+1:] = sorted(groups[ig+1:],key=sum,reverse=True)
                    spreading = True
                    break
                if spreading: break
            if spreading: break
        if not spreading and remSize < max(map(len,groups))-1:
            remSize  += 1
            spreading = True
            groups.sort(key=sum,reverse=True)           
    return groups

In order to optimally match the total value of removed items, the target "swapping" group needs a combination of item (indexes) that adds up to the smallest total that is within the specified range. By getting the combination with the smallest eligible total, the reduction of the source group's total is maximized and excess item values are progressively pushed down to the last groups. This function produces a list of indexes that meet that criteria:

# find group indexes producing smallest sum in range
def matchSum(g,minSum,maxSum):
    gsums = {0:[]}
    for i,n in enumerate(g):
        newSums = { s+n:[*ss,i] for s,ss in gsums.items() if s+n<=maxSum }
        gsums.update(newSums)
    sumVal  = min(gsums,key=lambda s:s if s>=minSum else maxSum+1)
    return gsums.get(sumVal,[])

Testing:

items = [ random.randint(50) for i in range(21)]
target = 150

groups = bonusGroups(items, target)

print("Items: {}".format(items))

for index, group in enumerate(groups, start=1):
    print("Group {}: {}, total: {}, length: {}".format(index, group, sum(group), len(group)))

Test outputs:

Items: [38, 38, 31, 9, 42, 25, 22, 42, 44, 46, 43, 47, 14, 20, 38, 34, 35, 3, 49, 36, 30]
Group 1: [49, 47, 46, 3, 9], total: 154, length: 5
Group 2: [44, 43, 42, 20, 14], total: 163, length: 5
Group 3: [42, 38, 38, 31, 22], total: 171, length: 5
Group 4: [25, 30, 34, 35, 36, 38], total: 198, length: 6

Items: [34, 5, 13, 30, 27, 15, 4, 44, 33, 13, 25, 41, 33, 23, 14, 8, 39, 9, 33, 8, 4]
Group 1: [44, 41, 39, 25, 4], total: 153, length: 5
Group 2: [34, 33, 33, 33, 15, 4], total: 152, length: 6
Group 3: [5, 8, 8, 9, 13, 13, 14, 23, 27, 30], total: 150, length: 10

Items: [25, 22, 44, 42, 43, 22, 25, 16, 42, 24, 21, 5, 4, 16, 3, 22, 46, 31, 11, 24, 14]
Group 1: [46, 44, 43, 16, 3], total: 152, length: 5
Group 2: [42, 42, 31, 25, 5, 4, 11], total: 160, length: 7
Group 3: [14, 16, 21, 22, 22, 22, 24, 24, 25], total: 190, length: 9

Answer 2

Here's an optimized approach which sorts the array in descending order, then tries to build the maximum subset possible before moving to the next subset. If the next item is too large, it moves on to the next one. It also incorporates dynamic programming, reducing the number of checks made.

from typing import List

def get_groups(item_list: List[int], target: int) -> List[List[int]]:
    groups = []
    remainder = []

    # sort list in descending order
    item_list.sort(reverse=True)

    while item_list:
        group = []
        for item in item_list[:]:
            if sum(group) + item <= target:
                group.append(item)
                item_list.remove(item)
        if group:
            groups.append(group)
        else:
            remainder = item_list
            break

    groups.append(remainder)

    return groups

# random generator is replaced with a static list for reproducibility
items = [1,2,3,4,5,6,7,8,9,10]
target = 5

groups = get_groups(items, target)

print("Items: {}".format(items))

for index, group in enumerate(groups, start=1):
    print("Group {}: {}, total: {}, length: {}".format(index, group, sum(group), len(group)))