Skip to main content
 首页 » 编程设计

Python:遍历受约束的所有整数组合(找到函数的最小值)

2024年11月01日8lautakyan007

我想找到一种方法返回所有向量[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 模块的链接。