CODEWITHSUNDEEP
python
Matthew Snell
Matthew Snell

Reputation: 957

Grouping values from list into buckets to keep sum of values at or below threshold

I have a list of times in minutes that represent the time it takes to do some job, but the amount of time spent working cannot exceed 240 minutes in any given day.I would like to separate into N groups such that the sum of the items in the group does not exceed the threshold (240 in this example).

An example list could be [60, 70, 90, 120, 180, 240]

One possible solution to the above list would be: [[240], [180, 60], [70, 90], [120]]. Note how each of the sums in each list does not exceed the threshold of 240 while leaving some leftover is fine, but how do I know this is the most optimal solution? Optimal being defined as simultaneously minimizing leftover and the number of buckets.

I've been working on trying to do this with some for loops in Python but it feels about as inefficient as possible. Also, due to the method of removing items from the list, the for loop isn't iterating over all values. Below is my attempt.

import random
import math

def roundup(x):
    return int(math.ceil(x / 10.0)) * 10

threshold = 240;

randomlist = []

for i in range(0,10):
    n = random.randint(30,240)
    randomlist.append(roundup(n))

days = []

print (randomlist)

for item in randomlist:
    schedule = []
    schedule.append(item)
    minutes_remaining = threshold - item
    for item2 in randomlist:
        if randomlist.index(item) != randomlist.index(item2):
            if item2 <= minutes_remaining:
                minutes_remaining -= item2
                schedule.append(item2)
                randomlist.remove(item2)
    randomlist.remove(item)
    days.append(schedule)

print (days)

Upvotes: 2

Views: 1082

Answers (3)

Mike O&#39;Connor
Mike O&#39;Connor

Reputation: 2710

from itertools import permutations 

l =[60, 70, 90, 120, 180, 240]

perm = permutations(l)

results = []
for p in perm:

    for i in range(1, len(p)):
        if sum(p[ : i]) <= 240:    
            results += [ tuple( sorted( p[ : i] ) ) ]

print(list(set(results)))

The printout is:

[(90,), (90, 120), (60, 70, 90), (180,), (60,), (120,), (60, 180), (240,), (70,), (70, 120), (60, 90), (70, 90), (60, 70), (60, 120)]

Upvotes: 0

Pramote Kuacharoen
Pramote Kuacharoen

Reputation: 1541

from itertools import permutations, product, accumulate

THRESHOLD = 240


def make_groups(lst, n):
    """
    Make n groups. The sum of the items in the group does not exceed 
    the threshold.
    """
    groups = []
    grps_range = [range(1, len(lst) - n + 2) for _ in range(n)]
    combo = [i for i in product(*grps_range) if sum(i) == len(lst)]
    for c in combo:
        marker = [0] + list(accumulate(c))
        group = [tuple(sorted(lst[i:j])) for i, j in zip(marker, marker[1:])]
        conform = [sum(g) <= THRESHOLD for g in group]
        if all(conform):
            groups.append(tuple(sorted(group)))

    return groups


def ngroups_leftover(entry):
    """
    Returns number of groups and sum of left over times
    """
    ngroups = len(entry)
    leftover = [THRESHOLD - sum(x) for x in entry]
    return ngroups, sum(leftover)


groups = []
l = [60, 70, 90, 120, 180, 240]
perm = permutations(l)
for p in perm:
    for i in range(1, len(p) + 1):
        result = make_groups(p, i)
        groups += result

unique_groups = set(groups)

x = sorted(unique_groups, key=ngroups_leftover)
# There are many solutions which result in the same number of groups
# and left over time. But, the first entry would do.
print(x[0])

Output

((60, 180), (70,), (90, 120), (240,))

All possible combinations:

[((60, 180), (70,), (90, 120), (240,)),
 ((60, 70), (90, 120), (180,), (240,)),
 ((60, 180), (70, 120), (90,), (240,)),
 ((60, 90), (70, 120), (180,), (240,)),
 ((60, 120), (70, 90), (180,), (240,)),
 ((60, 70, 90), (120,), (180,), (240,)),
 ((60, 180), (70, 90), (120,), (240,)),
 ((60, 180), (70,), (90,), (120,), (240,)),
 ((60,), (70, 90), (120,), (180,), (240,)),
 ((60, 70), (90,), (120,), (180,), (240,)),
 ((60,), (70, 120), (90,), (180,), (240,)),
 ((60, 120), (70,), (90,), (180,), (240,)),
 ((60, 90), (70,), (120,), (180,), (240,)),
 ((60,), (70,), (90, 120), (180,), (240,)),
 ((60,), (70,), (90,), (120,), (180,), (240,))]

Upvotes: 1

ooo
ooo

Reputation: 542

I have tried a Greedy solution O( N log(N) + N), not sure if it is Optimal.

inp = [60, 70, 90, 120, 180, 240]
inp.sort()

i =0
j = len(inp)-1
k = 240
while j >= i:
    tmp = []
    tmp.append(inp[j])
    sm = inp[j]
    while i < j:
        if sm + inp[i] > k:
            break
        sm += inp[i]
        tmp.append(inp[i])
        i+=1
    print(tmp)
    j-=1

Output:

[240]
[180, 60]
[120, 70]
[90]

Upvotes: 0

Related Questions