Python，两个列表之间元素相加的所有组合，有约束

Question

我有两个列表:

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 个元素？

谢谢。

Answer 1

您可以将递归与生成器一起使用，提供一个条件来检查累加和的运行值:

演示字符串表示的解决方案:

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