Как сделать, что бы скрипт искал только фиксированное количество слагаемых?

Question

[Canp]

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target: 
        print("sum(%s)=%s" % (partial, target))
    if s >= target:
        return  # if we reach the number why bother to continue
    
    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, partial + [n]) 
   

if __name__ == "__main__":
    subset_sum([40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86],12 + 70 +75 +80)

Код выдает и 5 и 3 слогаемых, а как сделать что бы искалось именно 4 слагаемых ?

Большое спасибо

Answer 1

[Wataru]

У вас все равно полный перебор, можно через itertools.combinations перебирать сочетания из заданного количества имеющихся чисел, считать их сумму и, если совпало, выводить. Там всего один цикл, буквально 4 строчки будет решение.

Но это может работать даже медленнее на некоторых входных данных чем проверка в конце вашего рекурсивного перебора, ибо тут нет ранних отсечений: вы будете перебирать заведомо большие искомой суммы.

Более хитрые и быстрые варианты: динамическое программирование типа задачи о рюкзаке, где вы считаете количество способов набрать такую-то сумму стольки-то слагаемыми из стольки-то первых чисел. А потом используя это в рекурсивном переборе можно отрубать его тупиковые ветви: если ДП говорит, что там 0 наборов, то можно туда не идти в рекурсии. Или, если вам не сами наборы, а из количество нужно, то даже рекурсивного перебора не надо. Но это работает, только если target не очень большое.

Второй более быстрый вариант: получить хоть бы и вашим перебором все варианты собрать все суммы среди первых n/2 чисел и отдельно среди оставшихся. Их надо распихать по разным массивам, в зависимости от количества слагаемых. Отсортировать по сумме. Потом перебрать, сколько чисел берем из первой половины, тогда понятно, сколько берем из второй. А потом двумя указателями, идущими навстречу в этих двух упорядоченных массивах можно за один проход найти все способы скомбинировать пару чисел из двух массивов, дающую искомую сумму.

Comments

[Canp]

у меня есть код на ДП, но мне его слишком сложно запустить..Итертуллз, он прежде чем хоть какойто результат выдать "думает" иногда несколько дней а результата так и нет....

Мне нужно 277 разложить чтобы первое слагаемое было 2, все слагаемые от 1 до 7. Пытаюсь найти все варианты уже 2 дня перебирает и когда закончится поиск не известно ...

[Wataru]

Canp, порядок слагаемых не важен?

[Canp]

Wataru, Здравствуйте. Порядок Важен.

[Canp]

меня "тычат" в итертуулз.

так вот скрит, он у меня час уже включен, даже печатать ничего не начал

import itertools
 

S = 227#int(input())
K =  52# int(input())
output = []
for perm in itertools.permutations(range(S + 1), K):
    if sum(perm) == S:
        output.append(f"+".join(str(i) for i in perm))
print(f"{S}=" + "=".join(output))

[Canp]

Wataru, я тут сократил немного, теперь у меня слагаемые это только числа от 1 до 7 и их всего 52 шт и сумма слагаемых не 8505, а 227. но все равно итертулз не тянет мой комп.

?

[Wataru]

Canp, Вы вообще представляете, сколько их там этих сочетаний? 7*10^51. Будет считать до тепловой смерти вселенной. Ваш исходный алгоритм, вообще-то тоже.

У вас, я так понял, задача другая. Набрать разбить число на слагаемые от 1 до 7.

Можно хоть и 6 вложенными циклами подсчитать (число 7-ок от 0 до 227//7. Число 6-ок от 0 до (227-7*num7)//6, Число 5-ок от 0 до сколько там влезает в оставшуюся часть числа. И т.д. Число 2 циклом,а число единиц - сколько осталось. Потом через тот же itertools.permutations генерируйте все варианты перемешать набор из num7 7-ок, num6 6-рок и т.д. Можно выходить из цикла если слагаемых слишком много, или если оставшехся чисел не хватит набрать слагаемые. Ну или короче рекурсией.

import itertools

def Gen(s, k, m, cur): # разбить S на K слагаемых от 1 до M
  if m == 1:
    if s != k: return
    new_list = list(cur)
    new_list.extend([1]*k)
    yield from set(itertools.permutations(new_list))
    #yield new_list # если порядок не важен
    return
  can_fit = min(s//m, k, (s-k)//(m-1))
  need_take = max(0, s-k*(m-1))
  new_list = list(cur)
  new_list.extend([m]*need_take)
  for i in range(need_take, can_fit+1):
    yield from Gen(s-m*i, k-i, m-1, new_list)
    new_list.append(m)

print(Gen(227, 52, 7, []))

Только там даже без перестановок 360 тысяч решений, и это умножается на какое-то офигенно большое число, ибо 52 слагаемых можно тасовать кучей способов. Там только одно из решений [5]*19+[4]*33 можно перетасовать 52!/19!/33! ~= 7*10^13 способами. Вы только его одно будете годами тасовать.

[Wataru]

Canp, У вас очевидно проблема XY. Вы что-то придумали как вашу исходную задачу решать, свели ее к этому и ищите решение вот этой другой задачи. А она решений не имеет. Если вам порядок важен, всех вариантов просто тупо слишком много.

[Canp]

Wataru, ошибка при запуске:

xman@localhost:~$ nano 09999.py xman@localhost:~$ python3 09999.py

generator object Gen at 0x7632a556d8 xman@localhost:~$

generator object Gen at 0x700c390e40

[Program finished]

можно ее исправить ?

БОЛЬШОЕ СПАСИБО ЗА ВАШИ ОТВЕТЫ !!!

[Wataru]

Canp,
сделайте for x : Gen(...) : print(x)

Answer 2

[Rsa97]

Очевидно, проверять количество слагаемых перед выводом.

Comments

[Canp]

интересует, не фильтровать нужное количество, а искать