2

我想找到一种方法来返回受约束 x_1+...+x_n=constant 约束的所有向量 [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

是否有任何可能已经执行此操作的功能或类似的功能？任何帮助或建议将不胜感激。

4

2 回答 2

2

蛮力解决方案如下：

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 变量解决方案可能会非常缓慢。您可能想研究线性编程技术。Cousera 网站上有一个关于线性优化的免费课程，可以用来更快地解决这类问题。

查看这个Stack Overflow 问题，了解作为整数约束求解器的 python 模块的链接。

于 2013-07-23T00:44:04.777 回答
0

您想查找给定整数的所有固定长度分区。这可以迭代地或递归地完成。递归算法背后的想法是添加一个辅助参数，表示允许在分区中的值的下限。然后，对于分区中每个可能的最小值，进行递归调用以找出构造分区其余部分的方法。

def fixed_length_partitions(n, k, min_value=0):
    """Yields all partitions of the integer n into k integers."""

    if k == 0:
        if n == 0:
            yield []
    else:
        for last_num in range(min_value, 1 + n//k):
            for nums in _flps(n-last_num, k-1, min_value=last_num):
                # Warning: mutative
                nums += [last_num]
                yield nums
_flps = fixed_length_partitions

迭代算法会快得多（避免大量 Python 函数调用开销），但可读性也较差，因为它本质上会用显式列表替换 Python 调用堆栈，最终使控制流更加混乱。

于 2013-07-23T01:42:25.727 回答