python - python 的行和列限制

Question

我有一个需要修改的列表m

我需要每行的总和大于A并且每列的总和小于B

我有这样的东西

x = 5     #or other number, not relevant
rows = len(m)
cols = len(m[0])

for r in range(rows): 
    while sum(m[r]) < A:  
        c = randint(0, cols-1)
        m[r][c] += x 

for c in range(cols): 
    cant = sum([m[r][c] for r in range(rows)])
    while cant > B:
        r = randint(0, rows-1)
        if m[r][c] >= x:  #I don't want negatives
            m[r][c] -= x

我的问题是:我需要满足这两个条件，这样，在第二个 for 之后，我将不确定是否仍然满足第一个条件。

关于如何满足这两个条件，当然还有最佳执行，有什么建议吗？我绝对可以考虑使用 numpy

编辑(示例)

#input
m = [[0,0,0],
    [0,0,0]]
A = 20
B = 25

# one desired output (since it chooses random positions)
m = [[10,0,15],
    [15,0,5]]

我可能需要添加

这是为了生成遗传算法的随机初始群体，限制是使它们成为可能的解决方案，我需要运行大约 80 次才能获得不同的可能解决方案

Answer 1

这样的事情应该能解决问题:

import numpy
from scipy.optimize import linprog

A = 10
B = 20
m = 2
n = m * m

# the coefficients of a linear function to minimize.
# setting this to all ones minimizes the sum of all variable
# values in the matrix, which solves the problem, but see below.
c = numpy.ones(n)

# the constraint matrix.
# This is matrix-multiplied with the current solution candidate
# to form the left hand side of a set of normalized 
# linear inequality constraint equations, i.e.
#
# x_0 * A_ub[0][0] + x_1 * A_ub[0][1] <= b_0
# x_1 * A_ub[1][0] + x_1 * A_ub[1][1] <= b_1
# ...
A_ub = numpy.zeros((2 * m, n))

# row sums. Since the <= inequality is a fixed component,
# we just multiply everthing by (-1), i.e. we demand that
# the negative sums are smaller than the negative limit -A.
#
# Assign row ranges all at once, because numpy can do this.
for r in xrange(0, m):
    A_ub[r][r * m:(r + 1) * m] = -1

# We want that the sum of the x  in each (flattened)
# column is smaller than B
#
# The manual stepping for the column sums in row-major encoding
# is a little bit annoying here.
for r in xrange(0, m):
    for j in xrange(0, m):
        A_ub[r + m][r + m * j] = 1

# the actual upper limits for the normalized inequalities.
b_ub = [-A] * m + [B] * m

# hand the linear program to scipy
solution = linprog(c, A_ub=A_ub, b_ub=b_ub)

# bring the solution into the desired matrix form
print numpy.reshape(solution.x, (m, m))

注意事项

• 我使用<= ，不是<正如你的问题所示，因为这就是 numpy 支持的。
• 这会最小化目标向量中所有值的总和。对于您的用例，您可能希望最小化距离到原始样本，线性程序无法处理，因为平方误差和绝对差都不能使用线性组合(这就是 c 代表的)来表示。为此，您可能需要完整地 minimize() 。

不过，这应该能让你有一个大概的了解。