Как найти все комбинации сумм в списке, которые дают целевое значение?
Нужно найти все комбинации сумм в списке, которые дают целевое значение.
Длина списка nums - до 30 элементов. В списке могут быть числа от 1 до 9 999 999.
Целевое значение target может быть от 1 до 9 999 999.
Для решения задачи дубликаты необходимо убрать. Сортировка списка выполняется только один раз и не тратит ресурсы.
def find_combination_2(nums: list, target):
result = []
nums = list(set(nums)) # Убираем дубликаты
nums.sort() # Сортируем список
for r in range(1, len(nums) + 1):
print(r)
for combo in combinations(nums, r):
current_sum = sum(combo)
if current_sum == target:
result.append(list(combo))
elif current_sum > target:
print(current_sum)
break # Выходим из цикла, если сумма превышает целевое значение
return result
Как можно ускорить выполнение функции без многопоточности?
Ответы (4 шт):
Попробуем так (похоже на алгоритм Meet-in-the-middle):
Разделим список на две части, и для каждой сгенерируем все возможные суммы, в том числе и пустую. Их будет не более, чем по 32768 в каждой части.
Затем для каждой суммы из левой части поищем дополнение в правой части. Если есть, то сгенерируем все пары комбинаций.
Для экономии храним комбинации в виде бинарных чисел, в которых единичные биты соответствуют индексам в соответствующем списке (честно говоря, это наследие экспериментов с недопущением пересечений, но переделывать на хранение самих чисел уже не стал)
Примеры включают пойманную комбинацию случайных чисел для списка длиной 30, которая даёт сравнительно длинный результат. Работает быстро.
Задача о наборе суммы при небольших целевых значениях может быть решена также динамическим программированием за время, пропорциональное target*len(nums)), и тут ещё понадобится время на хранение и проверку промежуточных комбинаций, его непросто оценить, и место target + хранение промежуточных комбинаций.
def find_combs(nums: list, target):
def unzipp(l, r):
p = []
t = l | (r<<(len(nums)//2))
b = 0
while t:
if t%2:
p.append(nums[b])
t //= 2
b += 1
return p
result = []
nums = list(set(nums)) # Убираем дубликаты
n = len(nums)
left = nums[0:n//2]
right = nums[n//2:]
leftdic = {}
for m in range(1<<len(left)):
t = m
s = 0
b = 0
while t:
if t%2:
s += left[b]
t //= 2
b += 1
if s not in leftdic:
leftdic[s] = []
leftdic[s].append(m)
#print(leftdic)
rightdic = {}
for m in range(1<<len(right)):
t = m
s = 0
b = 0
while t:
if t%2:
s += right[b]
t //= 2
b += 1
if s not in rightdic:
rightdic[s] = []
rightdic[s].append(m)
#print(rightdic)
for k in leftdic.keys():
t = target - k
if t in rightdic:
for l in leftdic[k]:
for r in rightdic[t]:
result.append(unzipp(l,r))
return result
print(find_combs([2,3,5,7,10,11,13], 21))
print(find_combs([3, 5, 7, 8, 9, 10, 11],25))
import random
a = [random.randint(1,10000000) for i in range(30)]
t = random.randint(1,150000000)
print(a, t)
a = [4687271, 450570, 1115149, 9839847, 7036317, 7247959, 9656662, 5275278, 2884715, 3446792, 1810765, 6462299, 538799, 4396281, 2774047, 4291174, 9304056, 857120, 5572892, 8158331, 1468953, 8955730, 6576077, 2684190, 509857, 6908856, 1566333, 9096332, 6276145, 4670849]
t = 60898739
g = find_combs(a, t)
print(len(g))
for c in g:
print(c)
------
[[10, 11], [3, 7, 11], [3, 5, 13], [2, 3, 5, 11]]
[[5, 9, 11], [3, 5, 8, 9], [7, 8, 10], [3, 5, 7, 10]]
24
[4670849, 3446792, 1115149, 5275278, 6908856, 1810765, 7247959, 6462299, 9839847, 4396281, 8158331, 1566333]
[4670849, 1115149, 5572892, 7036317, 2774047, 857120, 6276145, 6576077, 6462299, 4291174, 9304056, 4396281, 1566333]
[3446792, 7036317, 2684190, 2774047, 857120, 6576077, 8955730, 9656662, 6462299, 4291174, 8158331]
[4670849, 3446792, 1115149, 5275278, 7036317, 2684190, 509857, 6276145, 6576077, 6462299, 4291174, 4396281, 8158331]
[4670849, 450570, 5275278, 2774047, 857120, 509857, 6276145, 6908856, 1810765, 8955730, 7247959, 4291174, 9304056, 1566333]
[4670849, 3446792, 450570, 1468953, 2684190, 2774047, 857120, 509857, 6908856, 1810765, 9656662, 7247959, 4291174, 4396281, 8158331, 1566333]
[3446792, 1115149, 5275278, 1468953, 5572892, 2684190, 2774047, 857120, 509857, 8955730, 9656662, 4291174, 9839847, 2884715, 1566333]
[4670849, 3446792, 450570, 1115149, 5275278, 5572892, 7036317, 2774047, 4687271, 6908856, 9656662, 9304056]
[4670849, 5275278, 5572892, 2684190, 2774047, 857120, 4687271, 6276145, 6908856, 1810765, 9656662, 8158331, 1566333]
[4670849, 3446792, 450570, 5572892, 7036317, 2774047, 509857, 4687271, 6576077, 4291174, 9839847, 2884715, 8158331]
[4670849, 3446792, 450570, 9096332, 1115149, 1468953, 2684190, 2774047, 509857, 4687271, 1810765, 9656662, 4291174, 9839847, 4396281]
[4670849, 450570, 5275278, 7036317, 2684190, 857120, 509857, 4687271, 1810765, 8955730, 9839847, 4396281, 8158331, 1566333]
[4670849, 9096332, 1468953, 5572892, 538799, 6276145, 7247959, 6462299, 9839847, 8158331, 1566333]
[4670849, 450570, 9096332, 1468953, 2774047, 538799, 1810765, 6576077, 9656662, 4291174, 9839847, 8158331, 1566333]
[3446792, 450570, 5275278, 7036317, 2684190, 2774047, 538799, 6276145, 6908856, 8955730, 7247959, 9304056]
[4670849, 3446792, 450570, 9096332, 1115149, 5572892, 2684190, 857120, 538799, 6276145, 1810765, 6576077, 8955730, 2884715, 4396281, 1566333]
[4670849, 450570, 5275278, 1468953, 5572892, 2684190, 2774047, 857120, 538799, 6908856, 7247959, 9839847, 2884715, 8158331, 1566333]
[3446792, 450570, 1115149, 5275278, 1468953, 7036317, 2684190, 2774047, 857120, 538799, 1810765, 7247959, 6462299, 4291174, 2884715, 4396281, 8158331]
[1468953, 7036317, 509857, 538799, 6276145, 1810765, 6576077, 8955730, 7247959, 6462299, 4291174, 8158331, 1566333]
[9096332, 1468953, 7036317, 857120, 4687271, 538799, 6276145, 1810765, 6576077, 8955730, 4291174, 9304056]
[4670849, 450570, 1468953, 2774047, 857120, 4687271, 538799, 6276145, 1810765, 6576077, 7247959, 9839847, 9304056, 4396281]
[5572892, 2684190, 2774047, 857120, 4687271, 538799, 6276145, 6576077, 8955730, 9656662, 6462299, 4291174, 1566333]
[450570, 1115149, 5275278, 1468953, 7036317, 2684190, 2774047, 509857, 4687271, 538799, 1810765, 6576077, 8955730, 4291174, 9839847, 2884715]
[450570, 9096332, 1115149, 5572892, 2684190, 857120, 509857, 4687271, 538799, 6908856, 6576077, 6462299, 2884715, 4396281, 8158331]
NB Захотите использовать это решение, прочитайте сперва последнюю секцию.
Ошибки
Дубликаты убирать нельзя. Вызов find_combination_2([1, 1], 2) должен вернуть одно решение. Если убрать дубликаты, решения не будет совсем. С другой стороны плохо если вызов find_combination_2([1, 1, 1], 1) вернёт три одинаковых решения – три разные единицы из nums. Так что я бы сказал что дубликаты решений (не исходных чисел) надо убирать.
Ваша функция находит не все комбинации. Это всё из-за break в конце. Для nums = [1, 2, 3, 4, 5] и target = 5 она вернёт две комбинации: [5], [1, 4]. Если убрать break, будет найден ещё один ответ: [2, 3].
Производительность
Я тестировал вариант без break. На примерах где nums = list(range(1, n + 1)), target = n. Числа не дублируются, первый недостаток на ответе не сказывается.
n = int(input())
nums = list(range(1, n + 1))
target = n
for r in find_combination_2(nums, target):
print(r)
При увеличенни n на единицу время работы увеличивается примерно в два раза. Это естественно, если понять что перебирается 2n комбинаций слагаемых. Для n = 30 мой компьютер искал ответы одну минуту и сорок секунд.
Поиск может быть долгим. В текущем дизайне пользователь не увидит результат пока весь поиск не завершится. Вы сидите у экрана и не знаете сколько ещё ждать. Переделка функции в генератор смягчит этот недостаток: пользователь будет получать решения как только они будут доступны.
Рекурсивный поиск суммы:
def find_combination_3(nums, target):
expr = []
def search(i, s):
if i == len(nums):
if s == target:
yield expr
else:
expr.append(nums[i])
yield from search(i + 1, s + nums[i])
expr.pop()
yield from search(i + 1, s)
return search(0, 0)
Эта функция ищет все комбинации для тридцати слагаемых за три минуты пятьдесят секунд. То есть, он тратит 230 секунд на работу, которую ваша функция делала за 100 секунд. Такая себе оптимизация.
Но этот код можно оптимизировать: будем проверять что текущая сумма ещё не превысила целевую и что оставшихся слагаемых достаточно чтобы набрать целевую сумму:
def find_combination_4(nums, target):
expr = []
def search(i, low, high):
if not low <= target <= high:
return
if i == len(nums):
assert low == high
yield expr
else:
expr.append(nums[i])
yield from search(i + 1, low + nums[i], high )
expr.pop()
yield from search(i + 1, low , high - nums[i])
return search(0, 0, sum(nums))
И эта функция отыскивает все комбинации примерно за 0.01 секунды, то есть в десять тысяч раз быстрее чем поиск без проверок неравенств.
И это ещё не предел. Дело в том что на скорость поиска с условиями влияет порядок слагаемых в nums. Выгоднее первыми обрабатывать большие слагаемые. Тогда условие будет отсекать неудачные суммы раньше:
def find_combination_5(nums, target):
nums = sorted(nums, reverse=True)
expr = []
def search(i, low, high):
if not low <= target <= high:
return
if i == len(nums):
assert low == high
yield expr
else:
expr.append(nums[i])
yield from search(i + 1, low + nums[i], high )
expr.pop()
yield from search(i + 1, low , high - nums[i])
return search(0, 0, sum(nums))
В таком виде функция перебирает все ответы ещё в десять раз быстрее: за 0.001 секунды.
Добавлю вариант, которые правильно, как мне кажется, обрабатывает повторяющиеся слагаемые. Идейно всё тоже самое: рекурсивный поиск с отсечениями, но слагаемые предварительно группируются:
import collections
def find_combination_6(nums, target):
pairs = sorted(collections.Counter(nums).items(), reverse=True)
expr = []
def search(i, low, high):
if not low <= target <= high:
return
if i == len(pairs):
assert low == high
yield expr
else:
a, k = pairs[i]
high -= a * k
yield from search(i + 1, low, high)
for _ in range(k):
expr.append(a)
low += a
high += a
yield from search(i + 1, low, high)
del expr[-k:]
return search(0, 0, sum(a * k for a, k in pairs))
Самокритика
Пример, который я выбрал для демонстрации преимуществ рекурсивного поиска с отсечением очень хорошо демонстрирует его преимущества: "ускорение в десять тысяч раз" звучит хорошо. Вот другой пример, который показывает что иногда все ускорения яйца выеденного не стоят:
n = int(input())
nums = list(range(1001, 1001 + n))
target = 500 * n
for r in find_combination_6(nums, target):
print(r)
На этом примере большая часть оптимизаций превращается в тыкву. Две минуты для тридцати слагаемых. Мы вернулись туда откуда начинали, даже немного хуже. Опыт – сын ошибок трудных.
Поскольку
- мне не нравится мой собственный другой ответ к этому вопросу;
- и нравится идея из ответа MBo (поставьте ему плюсик);
- и не нравится код из ответа MBo (поставьте ему плюсик, если ещё не поставили);
- и хочется плюсиков,
то я хочу предложить своё решение. Список чисел разбивается на две половины, как именно – не важно. Для каждой половины строится словарь <сумма> → <список кортежей слагаемых с этой суммой>. Проходим по первому словарю, отыскиваем во втором дополнительные суммы. Если нашлась, печатаем все комбинации слагаемых из обоих словарей. Быстро и сердито (в смысле памяти):
from itertools import combinations
def sums(nums: list):
sums = {}
for r in range(len(nums) + 1):
for combo in combinations(nums, r):
sums.setdefault(sum(combo), []).append(combo)
return sums
def find_combination_7(nums, target):
d1 = sums(nums[:len(nums) // 2 ])
d2 = sums(nums[ len(nums) // 2:])
for k1, v1 in d1.items():
k2 = target - k1
v2 = d2.get(k2, [])
for e2 in v2:
for e1 in v1:
yield e1 + e2
Код грея
Небольшое улучшение к предыдущим ответам, точнее, асимптотически, существенное улучшение, но в случае Python оно не такое уж и большое, ввиду дорогих операций с int и сравнительно дешёвых sum() и list (у меня, примерно, -20..50% к find_combination_7() из ответа @Stanislav Volodarskiy).
Если порождать комбинации в порядке кода Грея, то каждая следующая комбинация сумм отличается от предыдущей на плюс/минус один элемент.
def sums_gray_iterator(nums: "Sequence[int]") -> "Iterator[tuple(int, int)]":
yield (0, 0)
if nums:
s = nums[0]
gray = 1
yield (s, gray)
for _ in range((1<<(len(nums) - 1)) - 1):
idx = (gray&-gray).bit_length() # Число младших 0-х бит, countr_zero()
diff = 1 << idx
if gray&diff:
s -= nums[idx]
else:
s += nums[idx]
gray ^= diff
yield (s, gray)
if gray&1:
s -= nums[0]
else:
s += nums[0]
gray ^= 1
yield (s, gray)
def find_combination_gray_i(nums: "Sequence[int]",
target: int) -> "Iterator[tuple[int]]":
mid = len(nums)//2
nums1 = nums[:mid]
nums2 = nums[mid:]
d1 = {}
for k1, e1 in sums_gray_iterator(nums1):
d1.setdefault(k1, []).append(e1)
for k2, e2 in sums_gray_iterator(nums2):
k1 = target - k2
if k1 in d1:
for e1 in d1[k1]:
yield (tuple(nums1[i] for i in range(len(nums1)) if e1&(1 << i)) +
tuple(nums2[i] for i in range(len(nums2)) if e2&(1 << i)))
Тесты (без удаления дубликатов):
def csorted(comb: "Sequence[Sequence[int]]") -> list[tuple[int]]:
res = set(tuple(sorted(c)) for c in comb)
return sorted(res)
def test_combination(f: "(Sequence[int], int) -> list[tuple[int]]",
without_duplicates=False) -> str:
if not without_duplicates:
assert csorted(f([1, 1], 2)) == [(1, 1)]
assert csorted(f([1, 2, 1], 2)) == [(1, 1), (2,)]
assert csorted(f([1, 2, 1, 0], 2)) == [
(0, 1, 1), (0, 2), (1, 1), (2,)
]
assert csorted(f([2,3,5,7,10,11,13], 21)) == [
(2, 3, 5, 11), (3, 5, 13), (3, 7, 11), (10, 11)
]
assert csorted(f([3, 5, 7, 8, 9, 10, 11],25)) == [
(3, 5, 7, 10), (3, 5, 8, 9), (5, 9, 11), (7, 8, 10)
]
assert csorted(f([
4687271, 450570, 1115149, 9839847, 7036317, 7247959, 9656662,
5275278, 2884715, 3446792, 1810765, 6462299, 538799, 4396281,
2774047, 4291174, 9304056, 857120, 5572892, 8158331, 1468953,
8955730, 6576077, 2684190, 509857, 6908856, 1566333, 9096332,
6276145, 4670849],60898739)) == [
(450570, 509857, 538799, 857120, 1115149, 2684190, 2884715, 4396281, 4687271,
5572892, 6462299, 6576077, 6908856, 8158331, 9096332),
(450570, 509857, 538799, 1115149, 1468953, 1810765, 2684190, 2774047, 2884715,
4291174, 4687271, 5275278, 6576077, 7036317, 8955730, 9839847),
(450570, 509857, 857120, 1468953, 1566333, 1810765, 2684190, 2774047, 3446792,
4291174, 4396281, 4670849, 6908856, 7247959, 8158331, 9656662),
(450570, 509857, 857120, 1566333, 1810765, 2684190, 4396281, 4670849, 4687271,
5275278, 7036317, 8158331, 8955730, 9839847),
(450570, 509857, 857120, 1566333, 1810765, 2774047, 4291174, 4670849, 5275278,
6276145, 6908856, 7247959, 8955730, 9304056),
(450570, 509857, 1115149, 1468953, 1810765, 2684190, 2774047, 3446792, 4291174,
4396281, 4670849, 4687271, 9096332, 9656662, 9839847),
(450570, 509857, 2774047, 2884715, 3446792, 4291174, 4670849, 4687271, 5572892,
6576077, 7036317, 8158331, 9839847),
(450570, 538799, 857120, 1115149, 1468953, 1810765, 2684190, 2774047, 2884715,
3446792, 4291174, 4396281, 5275278, 6462299, 7036317, 7247959, 8158331),
(450570, 538799, 857120, 1115149, 1566333, 1810765, 2684190, 2884715, 3446792,
4396281, 4670849, 5572892, 6276145, 6576077, 8955730, 9096332),
(450570, 538799, 857120, 1468953, 1566333, 2684190, 2774047, 2884715, 4670849,
5275278, 5572892, 6908856, 7247959, 8158331, 9839847),
(450570, 538799, 857120, 1468953, 1810765, 2774047, 4396281, 4670849, 4687271,
6276145, 6576077, 7247959, 9304056, 9839847),
(450570, 538799, 1468953, 1566333, 1810765, 2774047, 4291174, 4670849, 6576077,
8158331, 9096332, 9656662, 9839847),
(450570, 538799, 2684190, 2774047, 3446792, 5275278, 6276145, 6908856, 7036317,
7247959, 8955730, 9304056),
(450570, 1115149, 2774047, 3446792, 4670849, 4687271, 5275278, 5572892,
6908856, 7036317, 9304056, 9656662),
(509857, 538799, 1468953, 1566333, 1810765, 4291174, 6276145, 6462299, 6576077,
7036317, 7247959, 8158331, 8955730),
(509857, 857120, 1115149, 1468953, 1566333, 2684190, 2774047, 2884715, 3446792,
4291174, 5275278, 5572892, 8955730, 9656662, 9839847),
(509857, 1115149, 2684190, 3446792, 4291174, 4396281, 4670849, 5275278,
6276145, 6462299, 6576077, 7036317, 8158331),
(538799, 857120, 1468953, 1810765, 4291174, 4687271, 6276145, 6576077, 7036317,
8955730, 9096332, 9304056),
(538799, 857120, 1566333, 2684190, 2774047, 4291174, 4687271, 5572892, 6276145,
6462299, 6576077, 8955730, 9656662),
(538799, 1468953, 1566333, 4670849, 5572892, 6276145, 6462299, 7247959,
8158331, 9096332, 9839847),
(857120, 1115149, 1566333, 2774047, 4291174, 4396281, 4670849, 5572892,
6276145, 6462299, 6576077, 7036317, 9304056),
(857120, 1566333, 1810765, 2684190, 2774047, 4670849, 4687271, 5275278,
5572892, 6276145, 6908856, 8158331, 9656662),
(857120, 2684190, 2774047, 3446792, 4291174, 6462299, 6576077, 7036317,
8158331, 8955730, 9656662),
(1115149, 1566333, 1810765, 3446792, 4396281, 4670849, 5275278, 6462299,
6908856, 7247959, 8158331, 9839847)
]
return f"{f.__name__}: Хорь"
test_combination(find_combination_gray_i)
Numpy np.int32
Однако, есть векторизированый вариант, который хотя и имеет асимптотически худший объём чтения/записи памяти O(n⋅k⋅2**(n/2)) ≈ O(n2⋅2**(n/2)) бит, где k - разряднось входных данных (по смыслу задачи k >= n), но за счёт строгой минимизации обращений к памяти размером типа np.int32 и удобной векторизации, способен, если и не обогнать, то конкурировать на Python с асимптотически более шустрым вариантом кода Грея O((n + k)⋅2**(n/2)) ≈ O(n⋅2**(n/2)) бит.
import numpy as np
def sums_numpy(nums: "Sequence[int]", dtype=np.int32) -> "np.ndarray[dtype]":
idxs = np.array(range(2**len(nums)), dtype=dtype)
sums = np.zeros_like(idxs)
for i in range(len(nums)):
sums[0 != (idxs&(1 << i))] += nums[i]
return sums
def find_combination_numpy(nums: "Sequence[int]",
target: int,
dtype=np.int32) -> "Iterator[tuple[int]]":
mid = len(nums)//2
nums1 = nums[:mid]
nums2 = nums[mid:]
d1 = {}
k1 = sums_numpy(nums1, dtype=dtype)
for e1 in range(len(k1)):
d1.setdefault(k1[e1], []).append(e1)
k1 = target - sums_numpy(nums2, dtype=dtype)
for e2 in range(len(k1)):
if k1[e2] in d1:
for e1 in d1[k1[e2]]:
yield (tuple(nums1[i] for i in range(len(nums1)) if e1&(1 << i)) +
tuple(nums2[i] for i in range(len(nums2)) if e2&(1 << i)))
test_combination(find_combination_numpy)