查找列表元素的所有组合，包括重复元素

Question

我正在寻找一种 python 算法，它将返回数字列表的所有可能组合，该列表允许重复元素并加起来达到某个数字......

例如，给定目标数字 7，以及我希望能够生成以下组合的列表[2, 3, 4]：

2, 2, 3
2, 3, 2
3, 2, 2
3, 4
4, 3

我了解如何获取列表的所有可能组合，但我不知道如何以这种方式包含重复项。任何帮助将不胜感激！

Answer 1

您可以创建一个递归函数并应用必要的逻辑：

def combinations(d, current=[], sum_to = 7):
if sum(current) == 7:
yield current
else:
for i in d:
if sum(current+[i]) <= 7:
yield from combinations(d, current+[i])
print(list(combinations([2, 3, 4])))

输出：

[[2, 2, 3], [2, 3, 2], [3, 2, 2], [3, 4], [4, 3]]

Answer 2

这是一个蛮力解决方案：

def getAllSubsetsWithCertainSum(number_list, target_sum):
matching_numbers = []
def recursion(subset):
for number in number_list:
if sum(subset+[number]) < target_sum:
recursion(subset+[number])
elif sum(subset+[number]) == target_sum:
matching_numbers.append(subset+[number])
recursion([])
return matching_numbers

print(
getAllSubsetsWithCertainSum([2, 3, 4], 7)
)

如果输入 1，它还将返回 [1

， 1， 1， 1， 1， 1， 1， 1]

Answer 3

以前答案的变体，但有一个重要的区别：我们只找到与目标求和的排序组合，然后生成排列。带有[2,3,4]和7的示例：

• 第 1 步：查找[2,2,3]并[3,4]
• 第 2 步：生成排列：[[2, 2, 3], [2, 3, 2], [3, 2, 2], [3, 4], [4, 3]].

这真的更快。这是代码(permute_unique是从这里获取的，并通过列表理解进行了优化(：

def combinations2(d, sum_to):
def combinations_aux(d, current, sum_to):
for j in range(len(d)):
nex = current+[d[j]]
if sum(nex) == sum_to:
yield nex
elif sum(nex) < sum_to:
yield from combinations_aux(d[j:], nex, sum_to) # d[j:] for elements >= d[j]
def permute_unique(iterable):
# see https://stackoverflow.com/a/39014159/6914441
perms = [[]]
for i in iterable:
perms = [perm[:j] + [i] + perm[j:] 
for perm in perms 
for j in itertools.takewhile(lambda j:j<1 or perm[j-1] != i, range(len(perm) + 1))
]
return perms
return (p for c in combinations_aux(sorted(set(d)), [], sum_to) for p in permute_unique(c))

基准测试(来自 Ajax1234 的combinations(：

def one(): return list(combinations([2,3,4,5,6,7], 35))
def two(): return list(combinations2([2,3,4,5,6,7], 35))
assert sorted([tuple(t) for t in one()]) == sorted([tuple(t) for t in two()]) 
print (timeit.timeit(one, number=10))
# 154.99560340600146
print (timeit.timeit(two, number=10))
# 23.217042586999014