Argthtjtr

I have a list of numbers. Now if I set a fixed value V, is it possible for python to divide the list into several groups such that each group's sum is not smaller than V (get those groups as many as possible)?

Ex: if the list is [1,2,3,4,5] and the V is 6, then the result should be [[1,5],[2,3,4]]. Dividing the group means you cannot use the same original item more than once.

There's no limitation on how many items each sublist can contain and also the numbers are not in order (can be some random numbers). Could someone help me out? So far my solution is sum up all the combinations and compare the sums. But I'm pretty sure there should be a more effective solution. Thanks!

My solution: I kinda use this first and do the rest job by my mind, so it doesn't worth a further development.

import itertools

import math



stuff = list(range(10))

v = 6



for L in range(0, len(stuff)+1):

    for subset in itertools.combinations(stuff, L):

        if math.fsum(subset) > v: 

            print(subset,math.fsum(subset))

My solution has O(n^2) time complexity. You can sort list in ascending order. Then iterate over list from the end. As You want max number of subsets, then each value greater then V added to array. In other case collect values from right and left corners while achieve sum of subset equals to V:

def get_value_in_dict(d):

    return d.get(list(d)[0])



# Implementation for a list of dictionaries like [{'apple':1},{'pear':22},{'hat':23},{'glass':44}]

def sum_up_to_value(stuff, val):

    new_stuff = 

    sorted_stuff = list(sorted(stuff, key=lambda el: get_value_in_dict(el)))

    n = len(stuff)

    pointer_r = n - 1

    pointer_l = 0

    queue = list()



    while pointer_r >= pointer_l:

        if get_value_in_dict(sorted_stuff[pointer_r]) >= val:

            new_stuff.append([sorted_stuff[pointer_r]])

        else:

            subsum = get_value_in_dict(sorted_stuff[pointer_r])

            substuff = 

            while pointer_l < pointer_r and subsum < val:

                # get from queue

                while len(queue) and subsum < val:

                    temp = queue.pop(0)

                    subsum += get_value_in_dict(temp)

                    substuff.append(temp)

                # get from input

                else:

                    if subsum < val:

                        subsum += get_value_in_dict(sorted_stuff[pointer_l])

                        substuff.append(sorted_stuff[pointer_l])

                        pointer_l += 1

            substuff.append(sorted_stuff[pointer_r])

            # returns back smallest elements

            while subsum - get_value_in_dict(substuff[0]) >= val:

                temp = substuff.pop(0)

                queue.append(temp)

                subsum -= get_value_in_dict(substuff[0])



            if subsum < val:

                # add substuff to last element of new_stuff

                temp = new_stuff.pop()

                new_stuff.append(temp + substuff)

            else:

                new_stuff.append(substuff)

        pointer_r -= 1

    return new_stuff  # list(map(lambda el: sorted(el, key=lambda el_d: get_value_in_dict(el_d)), new_stuff)) for sorted by value elements in resulting list

If you sort your list, this should get you the desired result, although it's not very beautiful as I have to admit:

stuff = range(10)

l = len(stuff)

v = 6



new_stuff = 

i = 0

active = True



while active:

    sub_stuff = 

    subsum = 0

    while subsum<v:

        if i>(l-1):

            active = False

            break

        el = stuff[i]

        sub_stuff.append(el)

        subsum += el

        i += 1

    else:

        new_stuff.append(sub_stuff)

It just goes through your list and sums element until their sum is 6 or higher and then appends a list of those elements to new_stuff and goes on to find the next list.

Try a test list like:

import numpy as np

stuff = sorted(np.random.randint(0,10,100))