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

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

0 голосов
/ 04 марта 2019

У меня есть два списка: 

list1 = [1, 2, 3]
list2 = [0.5, 1]

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

list1 = [1+0.5, 2, 3]
list2 = [1, 2+0.5, 3]
list3 = [1, 2, 3+0.5]
list4 = [1+0.5, 2+0.5, 3]
list5 = [1, 2+0.5, 3+0.5]
list6 = [1+0.5, 2, 3+0.5]
list7 = [1+0.5, 2+0.5, 3+0.5]

list8 = [1+1, 2, 3]
list9 = [1,2+1,3]
list10 = [1,2,3+1]
list 11 = [1+1,2+1,3]
...
list = [1+0.5, 2+1, 3]
list = [1+0.5, 2, 3+1]
...

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

Есть ли хороший способ сделать это?Возможно, рекурсивно, учитывая, что в моем первоначальном списке будет около 30 элементов, а во втором - около 5?

Спасибо.

Ответы [ 2 ]

0 голосов
/ 04 марта 2019

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

Давайте рассмотрим просто одну группу lists.Представьте, что вы пробуете сценарий добавления к 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

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

0 голосов
/ 04 марта 2019

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

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

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)))

Вывод: 

[['1+0.5', '2+0.5', '3+0.5'], ['1+0.5', '2+0.5', 3], ['1+0.5', '2+0.5', '3+1'], ['1+0.5', '2+0.5', 3], ['1+0.5', 2, '3+0.5'], ['1+0.5', 2, 3], ['1+0.5', 2, '3+1'], ['1+0.5', 2, 3], ['1+0.5', '2+1', '3+0.5'], ['1+0.5', '2+1', 3], ['1+0.5', '2+1', '3+1'], ['1+0.5', '2+1', 3], ['1+0.5', 2, '3+0.5'], ['1+0.5', 2, 3], ['1+0.5', 2, '3+1'], ['1+0.5', 2, 3], [1, '2+0.5', '3+0.5'], [1, '2+0.5', 3], [1, '2+0.5', '3+1'], [1, '2+0.5', 3], [1, 2, '3+0.5'], [1, 2, 3], [1, 2, '3+1'], [1, 2, 3], [1, '2+1', '3+0.5'], [1, '2+1', 3], [1, '2+1', '3+1'], [1, '2+1', 3], [1, 2, '3+0.5'], [1, 2, 3], [1, 2, '3+1'], [1, 2, 3], ['1+1', '2+0.5', '3+0.5'], ['1+1', '2+0.5', 3], ['1+1', '2+0.5', '3+1'], ['1+1', '2+0.5', 3], ['1+1', 2, '3+0.5'], ['1+1', 2, 3], ['1+1', 2, '3+1'], ['1+1', 2, 3], ['1+1', '2+1', '3+0.5'], ['1+1', '2+1', 3], ['1+1', '2+1', '3+1'], ['1+1', '2+1', 3], ['1+1', 2, '3+0.5'], ['1+1', 2, 3], ['1+1', 2, '3+1'], ['1+1', 2, 3], [1, '2+0.5', '3+0.5'], [1, '2+0.5', 3], [1, '2+0.5', '3+1'], [1, '2+0.5', 3], [1, 2, '3+0.5'], [1, 2, 3], [1, 2, '3+1'], [1, 2, 3], [1, '2+1', '3+0.5'], [1, '2+1', 3], [1, '2+1', '3+1'], [1, '2+1', 3], [1, 2, '3+0.5'], [1, 2, 3], [1, 2, '3+1'], [1, 2, 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)))

Выход: 

[[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]]
...