生成一组随机数，在两种组合下形成总和

Question

我想生成 16 个随机非负整数，比如 a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p。

a+b+c+d = a particular sum
e+f+g+h = another sum
i+j+k+l = another sum
m+n+o+p = another sum

这很容易。但是，麻烦的是，

a+e+i+m = another sum
b+f+j+n = another sum
c+g+k+o = another sum
d+h+l+p = another sum

我在 Matlab 中编写了一个非常复杂的代码来生成满足条件的数字。该代码大约需要 0.5 秒，并在运行 1000 次迭代后生成大约 920 个这样的数组。数字 16 是一个原型。实际数字是 1794。所以，显然我所写的内容不会很有帮助。任何帮助都会很棒！

谢谢。

Answer 1

这个问题可以用随机加权成本函数的整数规划来解决，然后每次你运行这段代码，你都会得到不同的解决方案。

A = [A1; -A1; -eye(N)]
b = [sum1; sum2; ...; sumM ; -sum1; -sum2; ... ; -sumM; zeros(N,1)];
intcon = N;
f = randn(N,1);  %random cost function, will generate different solution everytime
solution = intlinprog(f,intcon,A,b);

其中 A1 是表示总和的矩阵，在您的示例中它将是

A1 = [1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0;
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0;
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0;
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0;
1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0;
0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0;
0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0;
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1];

简而言之，您将约束转换为 Ax <= b。

改进表示：

Aeq = A1
beq = [sum1; sum2; ...; sumM];
ub = inf*ones(N,1);
lb = zeros(N,1);
intcon = N;
f = randn(N,1);  %random cost function, will generate different solution everytime
solution = intlinprog(f,intcon,[],[], Aeq, beq, lb, ub);

生成一组随机数，在两种组合下形成总和

Generating a set of random numbers that form sum under two combinations

python

matlab

heuristics