(MATLAB) 线性方程的所有整数正解

Question

我想生成一个名为

listt

的列表，其中包含所有可能的正整数，总和为特定数字

d

。例如，我正在查看

x's

的所有可能正整数值的列表，使得

x1 + x2 + ... + xk = d

。

在这种情况下，

listt

的行大小应为

(d+k-1) choose (k-1)

。

我已经有了

MATLAB code

来执行此操作（见下文），但主要问题是此代码允许

listt

中重复行。 我需要帮助才能更改此代码，确保

listt

中没有重复的行。

k = 2;
d = 2;
m = nchoosek(d+k-1, k-1);

% generate non-negative integer random (m x k) array row-sum to d 
ss=rand(m,d+k-1);
[~,r] = maxk(ss,k-1,2);
z = zeros(m,1);
listt = diff([z, sort(r,2), (d+k)+z],1,2)-1;

我们说

d=5

和

k=2

。 假设我得到以下列表：

 1     4
 2     3
 0     5
 5     0
 5     0
 0     5

如您所见，行 (5,0) 和行 (0,5) 各重复两次。我想要获得独特的行。

更准确地说，对于

d=5

和

k=2

，我想要得到的到底是以下所有6种可能性：

 1     4
 2     3
 0     5
 5     0
 4     1
 3     2

任何帮助将不胜感激！

Answer 1

这称为整数分区。它以n为指数，Python中有一个很好的实现，https://ics.uci.edu/~eppstein/PADS/IntegerPartitions.py。

我找到了 MATLAB 实现，但从未使用过它：https://www.mathworks.com/matlabcentral/fileexchange/36437-integer-partition-generator

在这种情况下，listt的行大小应该是(d+k-1)选择(k-1)

不知道你是如何得到这个结果的，配分函数 p(n) 大约是

p(n) ~ 1/(4 n sqrt(3)) exp(pi sqrt(2 n / 3))

更新

如果您只需要具有特定长度的分区，那么您可以对给定的 d 运行分区算法，直到第一个输出超过 k 个数字。没有尝试 MATLAB 算法，但我尝试过的 Python 和其他算法都是从最短分区到最长分区。易于检查具体长度和断裂情况。

更新二

下载 MATLAB 包并使用 Octave 运行它。它有您想要的界面，例如

d = 6;
k = 3;

s=intpartgen(d,k);

已制作

6  0  0
5  1  0
4  1  1
3  2  1
4  2  0
2  2  2
3  3  0