Поиск уникальных комбинаций триплетов в предоставленном списке сумм - PullRequest
Новая
       19

Поиск уникальных комбинаций триплетов в предоставленном списке сумм

0 голосов
/ 19 апреля 2020

У меня есть ряд чисел, подобных этому 

lst = [30.25, 30.0, 19.0, 31.25, 28.25, 28.25, 29.25, 28.5, 26.5, 26.5, 25.25, 24.25, 23.75, 23.5, 20.5, 20.0, 21.75, 21.25, 21.0, 19.75, 20.0]

Теперь я хочу вычислить все такие возможные комбинации, сумма которых равна заданному числу (цель).

Я нашел это Очень мощная часть кода от fourtheye: 

def subsets_with_sum(lst, target, with_replacement=False):
    x = 0 if with_replacement else 1
    def _a(idx, l, r, t):
        if t == sum(l): r.append(l)
        elif t < sum(l): return
        for u in range(idx, len(lst)):
            _a(u + x, l + [lst[u]], r, t)
        return r
return _a(0, [], [], target)

Моя цель - очень хорошо, если есть комбинация из 3 или 4 (нужно выбрать до разрушения кода) списков с уникальными элементами из lst и для печати найден триплет или четверка.

Если нет: предложите 1 или 2 значения для достижения цели.

PS: как вы могли видеть, lst состоит из значения, которое является десятичным числом часов и для мой конкретный случай c моя цель - 168 (часов в неделю)

1 Ответ

1 голос
/ 19 апреля 2020

Использование itertools.combinations

from collections import defaultdict
import itertools

lst = [30.25, 30.0, 19.0, 31.25, 28.25, 28.25, 29.25, 28.5, 26.5, 26.5, 25.25, 24.25, 23.75, 23.5, 20.5, 20.0, 21.75, 21.25, 21.0, 19.75, 20.0]

def subsets_with_sum(lst, target, ncomb, nsuggest):
    # try to get match for ncomb
    matches = [comb for comb in itertools.combinations(lst, ncomb) if sum(comb) == target]
    if matches:
        return list(set(matches))

    # suggest values
    # build up dict of target - sum(comb)
    suggestions = defaultdict(int)
    for comb in itertools.combinations(lst, ncomb - 1):
        suggestion = target - sum(comb)
        if suggestion > 0:
            suggestions[suggestion] += 1
    sorted_suggestions = sorted([(value, key) for (key,value) in suggestions.items()], reverse=True)
    return [item[1] for item in sorted_suggestions[0:ncomb]]

Выход 

>>>subsets_with_sum(lst, 115, 4, 2)                                                                                 
[(30.25, 30.0, 28.25, 26.5),
 (30.0, 31.25, 28.5, 25.25),
 (30.25, 31.25, 28.25, 25.25),
 (30.25, 30.0, 31.25, 23.5),
 (30.25, 31.25, 29.25, 24.25),
 (30.0, 28.25, 28.25, 28.5)]

>>>subsets_with_sum(lst, target=215, ncomb=4, nsuggest=2)                                                                                 
[140.25, 138.5]
...