Python, все комбинации добавления элементов между двумя списками, с ограничением

Вы можете использовать рекурсию с генератором, предоставляя условие для проверки текущего значения накопленной суммы:

Решение с представлением демонстрационной строки:

def pairs(a, b, _l, _c = []):
  if len(_c) == _l:
    yield _c
  else:
     if a:
       for i in b:
         yield from pairs(a[1:], b, _l, _c=_c+[f'{a[0]}+{i}'])
         yield from pairs(a[1:], b, _l, _c= _c+[a[0]])

print(list(pairs([1, 2, 3], [0.5, 1], 3)))

Выход:

Решение с добавлением и сокращением:

def pairs(a, b, _l, _c = [], _sum=0):
  if len(_c) == _l:
    yield _c
  else:
    if a:
      for i in b:
        if a[0]+i+_sum < 8:
          yield from pairs(a[1:], b, _l, _c=_c+[a[0]+i], _sum=_sum+a[0]+i)
        if a[0]+_sum < 8:
          yield from pairs(a[1:], b, _l, _c= _c+[a[0]], _sum=_sum+a[0])

print(list(pairs([1, 2, 3], [0.5, 1], 3, _sum=0)))

Вывод:

[[1.5, 2.5, 3.5], [1.5, 2.5, 3], [1.5, 2.5, 3], [1.5, 2, 3.5], [1.5, 2, 3], [1.5, 2, 4], [1.5, 2, 3], [1.5, 3, 3], [1.5, 3, 3], [1.5, 2, 3.5], [1.5, 2, 3], [1.5, 2, 4], [1.5, 2, 3], [1, 2.5, 3.5], [1, 2.5, 3], [1, 2.5, 4], [1, 2.5, 3], [1, 2, 3.5], [1, 2, 3], [1, 2, 4], [1, 2, 3], [1, 3, 3.5], [1, 3, 3], [1, 3, 3], [1, 2, 3.5], [1, 2, 3], [1, 2, 4], [1, 2, 3], [2, 2.5, 3], [2, 2.5, 3], [2, 2, 3.5], [2, 2, 3], [2, 2, 3], [2, 2, 3.5], [2, 2, 3], [2, 2, 3], [1, 2.5, 3.5], [1, 2.5, 3], [1, 2.5, 4], [1, 2.5, 3], [1, 2, 3.5], [1, 2, 3], [1, 2, 4], [1, 2, 3], [1, 3, 3.5], [1, 3, 3], [1, 3, 3], [1, 2, 3.5], [1, 2, 3], [1, 2, 4], [1, 2, 3]]

Редактирование: указание нижней границы:

def pairs(a, b, _l, _c = [], _sum=0):
  if len(_c) == _l:
    if _sum > 2:
      yield _c
  else:
    if a:
      for i in b:
        if a[0]+i+_sum < 8:
          yield from pairs(a[1:], b, _l, _c=_c+[a[0]+i], _sum=_sum+a[0]+i)
        if a[0]+_sum < 8:
          yield from pairs(a[1:], b, _l, _c= _c+[a[0]], _sum=_sum+a[0])

print(list(pairs([1, 2, 3], [-1, 1], 3, _sum=0)))

Вывод: [1112 ]

[[0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 1, 3], [0, 2, 2], [0, 2, 3], [0, 2, 4], [0, 2, 3], [0, 3, 2], [0, 3, 3], [0, 3, 4], [0, 3, 3], [0, 2, 2], [0, 2, 3], [0, 2, 4], [0, 2, 3], [1, 1, 2], [1, 1, 3], [1, 1, 4], [1, 1, 3], [1, 2, 2], [1, 2, 3], [1, 2, 4], [1, 2, 3], [1, 3, 2], [1, 3, 3], [1, 3, 3], [1, 2, 2], [1, 2, 3], [1, 2, 4], [1, 2, 3], [2, 1, 2], [2, 1, 3], [2, 1, 4], [2, 1, 3], [2, 2, 2], [2, 2, 3], [2, 2, 3], [2, 3, 2], [2, 2, 2], [2, 2, 3], [2, 2, 3], [1, 1, 2], [1, 1, 3], [1, 1, 4], [1, 1, 3], [1, 2, 2], [1, 2, 3], [1, 2, 4], [1, 2, 3], [1, 3, 2], [1, 3, 3], [1, 3, 3], [1, 2, 2], [1, 2, 3], [1, 2, 4], [1, 2, 3]]

То, что вы описываете, невозможно без особых более строгих ограничений (и, возможно, даже тогда).

Давайте рассмотрим только одну группу list с. Представьте, что вы пробуете сценарий добавления к 15 индексам из 30 со всеми пятью возможными значениями в игре. Это 5 ^{15 (более 30 миллионов) способов заполнения 15 выбранных индексов, а 30 выбирают 15 наборов индексов для заполнения (более 155 миллионов), что объединяет 4 733 811 035 156 250 000 (4,7 квинтиллиона) списков. Может быть немного меньше, так как у вас будет ограничение на использование каждого из пяти значений хотя бы один раз (в противном случае вы пересчитаете одно и то же list с меньшим набором выбранных значений), но это все равно будет безумно. И это только для индекса 15, пять значений; другие будут несколько меньше, но большинство все равно будет невозможно вычислить по отдельности при жизни человека, не говоря уже о вычислимости в совокупности.}

Вы могли бы попытаться отфильтровать его несколькими способами, превентивно вычисляя сумму вашего большого ввода list, и пропуская любую комбинацию значений, которая гарантированно превысит ваше максимальное совокупное значение, а также упреждающе уменьшив кратность. любой ценности, которая подтолкнет вас через кепку. Но это сильно пахнет проблемой XY ; всякий раз, когда вы рассматриваете этот уровень комбинаторного безумия, у вас, вероятно, есть лучший способ выполнить вашу задачу (и / или ваша задача невозможна).

Для вашего простого случая вы просто комбинируете itertools инструменты, чтобы сделать это:

from itertools import combinations, product

def make_lists(list1, list2, limit):
    maxvalues = limit - sum(list1)
    minlist2 = min(list2)
    for numindices in range(1, len(list1)+1):
        if minlist2 * numindices >= maxvalues:
            continue
        for indices in combinations(range(len(list1)), numindices):
            for values in product([x for x in list2 if x < maxvalues], repeat=numindices):
                if sum(values) >= maxvalues:
                    continue
                newlist = list1[:]
                for i, v in zip(indices, values):
                    newlist[i] += v
                yield newlist

Но это займет время «тепловой смерти вселенной» для любой значимой входной длины. Рекурсивные решения могут более эффективно отфильтровывать недействительные выходные данные, но если ограничение не будет действительно строгим, вы все равно умрете до завершения программы.