S
S
site_trouble2018-02-15 13:35:19
JavaScript
site_trouble, 2018-02-15 13:35:19

How to group an array?

Good afternoon. There is an array of numbers:
[6, 4, 4, 3, 2, 1.5, 1, 0.5]
You need to ungroup by rows so that in each row the sum of the numbers is no more than 6.
It should turn out something like this:

[6]
[4, 2]
[4, 1.5, 0.5]
[3,1]

Any ideas how this can be done? Maybe there are algorithms ready for this task?

Answer the question

In order to leave comments, you need to log in

1 answer(s)
D
Dmitry, 2018-02-15
@site_trouble

To my "algorithm" from the comments, I can give the following code in python:
(I saw that the question was tagged "JAVASCRIPT", but it's better than no code at all)

from itertools import combinations

def ungroup(data_list, limit):
    data_list.sort()
    result_list = []
    while sum(data_list) > limit:
        series = [data_list.pop()]
        rest = limit - series[0]
        if rest == 0:
            result_list.append(series)
        elif rest in data_list:
            result_list.append(series + [data_list.pop(data_list.index(rest))])
        else:
            sublist = data_list.copy()
            for i in data_list:
                if i > rest:
                    sublist = data_list[:data_list.index(i)]
                    break
            for n in range(2, len(sublist)):
                comb = {sum(i): i for i in combinations(sublist, n)}
                if rest in comb.keys():
                    series.extend(comb[rest])
                    for i in comb[rest]: data_list.remove(i)
                    break
            result_list.append(series)
    if len(data_list) > 0:
        result_list.append(data_list)
    return result_list

print(ungroup([6, 4, 4, 3, 2, 1.5, 1, 0.5], 6))
# 

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question