我想找到一种方法返回所有向量[x_1,...,x_n]的集合受制于x_1+...+x_n=常数,每个x_i是一个非负整数,顺序不没关系。 (所以 [1,1,1,2]=[2,1,1,1])。我的编程经验很少,但过去一个月左右我一直在使用 Python (sage)。
特别是,我试图在非负整数(受约束)上找到 15 变量(对称)函数的最小值,但我想编写一个程序来完成它,因为我可以使用它也适用于类似的项目。
我已经尝试编写一个程序 4 天了,我突然意识到我必须以某种方式递归地定义我的函数……但我不知道该怎么做。我有一个代码可以做一些类似于我想要的事情(但它还没有完成)。我会发布它,即使我确定这是做我想做的事情的最低效方式:
def each_comb_first_step(vec):
row_num=floor(math.fabs((vec[0,vec.ncols()-1]-vec[0,vec.ncols()-2]))/2)+1
mat=matrix(ZZ, row_num, vec.ncols(), 0)
for j in range(row_num):
mat[j]=vec
vec[0,vec.ncols()-2]=vec[0,vec.ncols()-2]+1
vec[0,vec.ncols()-1]=vec[0,vec.ncols()-1]-1
return mat
def each_comb(num,const):
vec1=matrix(ZZ,1,num,0)
vec1[0,num-1]=const
time=0
steps=0
subtot=0
for i in (2,..,num-1):
steps=floor(const/(i+1))
for j in (1,..,steps):
time=j
for k in (num-i-1,..,num-2):
vec1[0,k]=time
time=time+1
subtot=0
for l in range(num-1):
subtot=subtot+vec1[0,l]
vec1[0,num-1]=const-subtot
mat1=each_comb_first_step(vec1)
return mat1
是否有任何机会已经执行此操作或类似操作?任何帮助或建议将不胜感激。
请您参考如下方法:
暴力解决方案如下:
import itertools as it
# Constraint function returns true if inputs meet constraint requirement
def constraint(x1, x2, x3, x4):
return x1 + x2 + x3 + x4 == 10
numbers = range(1,10) #valid numbers (non-negative integers)
num_variables = 4 #size of number tuple to create
#vectors contains all tuples of 4 numbers that meet constraint
vectors = [t for t in it.combinations_with_replacement(numbers, num_variables)
if constraint(*t)]
print vectors
输出
[(1, 1, 1, 7), (1, 1, 2, 6), (1, 1, 3, 5), (1, 1, 4, 4), (1, 2, 2, 5), (1, 2, 3, 4), (1, 3, 3, 3), (2, 2, 2, 4), (2, 2, 3, 3)]
运行时间为 O(numbers**num_variables),因此您的 15 变量解决方案可能会非常慢。您可能想研究线性规划技术。 Linear Optimization上有免费类(class)在 Cousera 网站上可以用来更快地解决这类问题。
看看这个 Stack Overflow question用于指向作为整数约束求解器的 python 模块的链接。
