Наименьшие подмножества с суммой, превышающей значение в python

Каков самый быстрый способ, учитывая список списков разных размеров, найти все наименьшие подмножества с суммой, большей или равной определенному значению?

Так что если набор и значение равны

A = [[1],[1,2,3,4],[5,6],[10],[1000,12],[11]]
value = 10

Решение было бы

res = [[10],[11]]

или еще раз:

A = [[1,10],[1,2,3,4],[5,6],[10,10],[1000,12,1],[1,10,11]]
value = 10
res = [[1,10],[10,10]]

заранее спасибо

Не могли бы вы поделиться способом, который вы нашли и который недостаточно быстр? Или что именно означает быстро?

CristiFati 09.04.2022 11:34

Я не нашел способ в данный момент

jahnLudvik 09.04.2022 11:34

Скорее всего вы знаете, что вы должны представить свои собственные попытки ([SO]: Как создать минимальный воспроизводимый пример (reprex (mcve))). Я уверен, что вы точно сможете что-то придумать (даже частичное решение).

CristiFati 09.04.2022 11:44
Анализ настроения постов в Twitter с помощью Python, Tweepy и Flair
Анализ настроения постов в Twitter с помощью Python, Tweepy и Flair
Анализ настроения текстовых сообщений может быть настолько сложным или простым, насколько вы его сделаете. Как и в любом ML-проекте, вы можете выбрать...
7 лайфхаков для начинающих Python-программистов
7 лайфхаков для начинающих Python-программистов
В этой статье мы расскажем о хитростях и советах по Python, которые должны быть известны разработчику Python.
Установка Apache Cassandra на Mac OS
Установка Apache Cassandra на Mac OS
Это краткое руководство по установке Apache Cassandra.
Сертификатная программа "Кванты Python": Бэктестер ансамблевых методов на основе ООП
Сертификатная программа "Кванты Python": Бэктестер ансамблевых методов на основе ООП
В одном из недавних постов я рассказал о том, как я использую навыки количественных исследований, которые я совершенствую в рамках программы TPQ...
Создание персонального файлового хранилища
Создание персонального файлового хранилища
Вы когда-нибудь хотели поделиться с кем-то файлом, но он содержал конфиденциальную информацию? Многие думают, что электронная почта безопасна, но это...
Создание приборной панели для анализа данных на GCP - часть I
Создание приборной панели для анализа данных на GCP - часть I
Недавно я столкнулся с интересной бизнес-задачей - визуализацией сбоев в цепочке поставок лекарств, которую могут просматривать врачи и...
0
3
33
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Вы можете использовать следующий код Python: код находит список длин в A затем проверяет подсписки в порядке возрастания, т. е. подсписки размера 1, затем размера 2 и затем размера 4. Обратите внимание, что код не проверяет более крупные подсписки, если в результат уже включен меньший подсписок.

A = [[1],[1,2,3,4],[5,6],[10],[1000,12],[11]]
value = 10

lens = list(set([len(i) for i in A]))   #result = [1,2,4]
res = []
for l in lens:
    if len(res) == 0: 
        for i in A: 
            if len(i) == l: 
                if sum(i) >= value: 
                    res.append(i)
print(res)   #result = [[10], [11]]   
      

Вот о чем я говорил в своем (2nd) комментарии. Используйте простое понимание списка, чтобы найти все подсписки, которые удовлетворяют условию:

>>> lists = [[1], [1, 2, 3, 4], [5, 6], [10], [1000, 12], [11]]
>>> value = 10
>>>
>>> [l for l in lists if sum(l) >= value]
[[1, 2, 3, 4], [5, 6], [10], [1000, 12], [11]]

Итак, у нас есть что-то, что работает, но может считаться медленным (ну, не этот конкретный пример, а для больших списков). Он медленный, потому что ищет все подсписки, которые удовлетворяют условию, тогда как на самом деле следует пытаться использовать только подсписки длина 1 (в данном случае).

1st вещь, которая приходит мне на ум, — это сортировка подсписков во входном списке в зависимости от их длины. Но сама сортировка тоже может быть медленной, и нам нужно только сгруппировать их. Один из способов — использовать словарь, где ключи — это длины, а значения — это списки подсписков с такой длиной:

>>> d = {}
>>> for l in lists:
...     d.setdefault(len(l), []).append(l)
...
>>> d
{1: [[1], [10], [11]], 4: [[1, 2, 3, 4]], 2: [[5, 6], [1000, 12]]}
>>>
>>> ret = []
>>>
>>> for i in sorted(d):  # Traverse the (sorted) lengths
...     for l in d[i]:
...         if sum(l) >= value:
...             ret.append(l)
...     if ret:  # Once a specific length was handled, if there are some results, simply stop
...         break
...
>>>
>>> ret
[[10], [11]]

Или, как функция:

def filter_sublists(sublists, min_sum_threshold):
    d = {}
    for l in sublists:
        d.setdefault(len(l), []).append(l)
    ret = []
    for i in sorted(d):
        for l in d[i]:
            if sum(l) >= min_sum_threshold:
                ret.append(l)
        if ret:
            break
    return ret

Другие вопросы по теме