我有一个组合数学的问题：设m＝(m1，…，mk(是k个正整数的向量。如果对于所有1≤i≤k，ai≤mi，则n的k组成(a1，…，ak(是m约束的。例如，(1,1,3(和(2,1,2(是5的唯一(2,1,4(-约束的3部分。
写一个函数constrained_components，它取一个自然数n和一个k个正整数的向量m，并打印n的所有m约束的k组成的集合。注意，k可以从m推断出来。
谷歌搜索发现了这个有用的功能：
def compositions(k, n):
# inputs: k and n are of type 'int'
# output: a set of tuples
assert n > k > 1
to_process = [[i] for i in range(1, n+1)]
while to_process:
l = to_process.pop()
s = sum(l)
le = len(l)
for i in range(1, n-s+1):
news = s + i
if news <= n:
newl = list(l)
newl.append(i)
if le == k-1 and news == n:
yield tuple(newl)
elif le < k-1 and news < n:
to_process.append(newl)
并实现以获得匹配约束的元组，如下所示：
def constrained_compositions(n, m):
# inputs: n is of type 'int' and m is a list of integers
# output: a set of tuples
k = len(m)
max_num = max(m)
l = []
comp = list(compositions(k,n))
for i in comp:
for j in i:
if j <= max_num:
l.append(i)
print(set(l))
但这是我的结果：
{(2, 3, 2), (2, 1, 4), (4, 2, 1), (5, 1, 1), (3, 3, 1), (3, 2, 2), (3, 1, 3), (1, 5, 1), (1, 4, 2), (2, 2, 3), (2, 4, 1), (1, 2, 4), (4, 1, 2), (1, 1, 5), (1, 3, 3)}
应该是：
{(1, 1, 5), (1, 2, 4), (2, 1, 4), (2, 2, 3), (3, 1, 3), (3, 2, 2)}
提前感谢你的帮助？
代码中有一部分有点偏离，那就是您只考虑m中的最大值，并根据它检查组合中的所有元素，而不考虑它们的实际位置。
这里有一个递归生成器，它直接生成受约束的合成：
def constrained_compositions(n, m):
if n == 0 and not m:
yield ()
if n < 0 or not m:
return
for i in range(1, min(n, m[0])+1):
for cc in constrained_compositions(n-i, m[1:]):
yield (i,) + cc
>>> list(constrained_compositions(7, [3, 2, 5]))
[(1, 1, 5), (1, 2, 4), (2, 1, 4), (2, 2, 3), (3, 1, 3), (3, 2, 2)]
这定义了成功和失败的基本情况。否则，它确保组成i的第一个元素在给定的限制<= m[0]内，并与n和m的余数一起递归：n-i和m[1:]
这对我来说很好：
def constrained_compositions(n, m):
C = set()
def help_comp(k, l):
D = set()
if k == 1:
for i in range(m[0]):
D.add((i+1,))
else:
for j in help_comp(k=k-1, l=l):
for i in range(m[(len(list(j)))]):
i=i+1
if i <= m[(len(list(j)))]:
D.add((j)+(i,))
return D
if len(m) == 1 & m[0] != n:
return C
if n == 0 and m[0] !=n:
return C
if len(m) == 1 and m[0] == n:
C.add((n,))
else:
for i in range(m[-1]):
i=i+1
for j in help_comp(k=len(m)-1, l=n):
if sum(list((i,)+(j))) == n:
if i <= m[-1]:
C.add((j)+(i,))
return C