获取加权项的排列，这些加权项加起来一定数量

Question

元素A权重为1，元素B权重为2。我需要找到A和B的可能排列，它们加起来一定量

例如，当所需金额为4时，我希望得到的是：

[A, A, A, A] 
[B, B]  
[B, A, A]  
[A, B, A]  
[A, A, B]

做这样的事情最好的方法是什么？起初，我试图通过使用itertools.permutations和手动检查求和（效率很低，但我不确定还能去哪里）来强制执行它，但对于更大的数字，这是不可能的。如果可能的话，我想知道一种不导入itertools或其他库的方法

Answer 1

你要找的不是排列，而是组合。置换是在不重复的情况下重新排列有限的元素集，而组合是假定n元素之一的m字段中的每一个，在python中用itertools.computations_with_replacement表示。在代码方面：

import itertools
from functools import reduce

elements = {"A": 1, "B": 2, "C": 1}
sum_restriction = lambda x: sum(elements[i] for i in x)==4
max_els = 4 // min(elements.values()) + 1

res = reduce(lambda x,y:x+y,[list(filter(sum_restriction, itertools.combinations_with_replacement(elements.keys(), i))) for i in range(max_els+1)])

我的示例返回：

>>> res
[('B', 'B'), ('A', 'A', 'B'), ('A', 'B', 'C'), ('B', 'C', 'C'), ('A', 'A', 'A', 'A'), ('A', 'A', 'A', 'C'), ('A', 'A', 'C', 'C'), ('A', 'C', 'C', 'C'), ('C', 'C', 'C', 'C')]