查找多个变量的所有组合总和为 1

我正在尝试解方程

x1 + x2 + x3 + .... + xn = 1

其中所有的值xi仅限于[0, 0.1, 0.2, ..., 0.9, 1].

目前，我通过首先生成一个n维数组来解决问题mat，其中每个元素位置的值是轴值的总和，其变化范围为axisValues = 0:0.1:1:

mat(i,j,k,...,q) = axisValues(i) + axisValues(j) + ... + axisValues(q).

然后我搜索结果数组中所有等于 1 的条目。该代码（如下所示以进一步说明）运行良好，并且已针对最多 5 个维度进行了测试。问题是，运行时间呈指数增长，我需要脚本在多个维度上工作。

clear all
dim = 2; % The dimension of the matrix is defined here. The script has been tested for dim ≤ 5
fractiles(:,1) = [0:0.1:1]; % Produces a vector containing the initial axis elements, which will be used to calculate the matrix elements
fractiles = repmat(fractiles,1,dim); % multiplies the vector to supply dim rows with the axis elements 0:0.1:1. These elements will be changed later, but the symmetry will remain the same.
dim_len = repmat(size(fractiles,1),1,size(fractiles,2)); % Here, the length of the dimensions is checked, which his needed to initialize the matrix mat, which will be filled with the axis element sums
mat = zeros(dim_len); % Here the matrix mat is initialized
Sub=cell(1,dim);
mat_size = size(mat);
% The following for loop fills each matrix elements of the dim dimensional matrix mat with the sum of the corresponding dim axis elements.
for ind=1:numel(mat)
    [Sub{:}]=ind2sub(mat_size,ind);
    SubMatrix=cell2mat(Sub);
    sum_indices = 0;
    for j = 1:dim
        sum_indices = sum_indices+fractiles(SubMatrix(j),j);
    end
    mat(ind) = sum_indices;
end
Ind_ones = find(mat==1); % Finally, the matrix elements equal to one are found.

我感觉以下使用问题对称性的想法可能有助于显着减少计算时间：

对于二维矩阵，满足上述条件的所有条目都位于对角线上mat(1,11) to mat(11,1)，即从最大值x1到最大值x2.

对于 3D 矩阵，所有条目都满足位于对角平面上的条件mat(1,1,11), mat(1,11,1), mat(11,1,1)，即从最大值x1 and x2到最大值x3.

对于更高维度也是如此：所有感兴趣的矩阵元素都位于n-1维度超平面固定在每个维度的最高轴值上。

问题是：有没有办法直接确定这些元素的索引？n-1维度超平面？如果是这样，整个问题就可以一步解决，而不需要计算 n 维矩阵的所有条目，然后搜索感兴趣的条目。

Math:

我们不采用超立方体的方式，而是求解方程

x(1) + x(2) + ... + x(n) = 1

其中每个x(i)可以变化[0, 1/k, 2/k, ... (k-1)/k, 1]反而。在你的情况下k将为 10，因为这将得出百分比[0, 10, 20, ... 90, 100]。 乘以k这对应于丢番图方程

x(1) + x(2) + ... + x(n) = k,

哪里所有的x(i)各有不同[0, 1, 2, ... k-1, k].

我们可以在它和组合概念之间建立双射与重复的组合 http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition.

维基百科文章甚至含蓄地提到了该语句的潜在双射：

大小为 k 的多重子集的数量就是丢番图方程的非负整数解的数量x1 + x2 + ... + xn = k.

对于一个较小的例子，假设我们要使用k=3和百分比[0, 33, 66, 100]反而。给定集合的所有 k 多重组合{1,2,3}:

RepCombs = 
     1     1     1
     1     1     2
     1     1     3
     1     2     2
     1     2     3
     1     3     3
     2     2     2
     2     2     3
     2     3     3
     3     3     3

然后我们使用以下规则将这些映射到您的百分比： 对于每一行i，如果输入的是j， 然后加1/3对应矩阵条目的百分比M(i,j)。第一行将对应于[1/3 + 1/3 + 1/3, 0, 0] = [1,0,0]。 此过程生成的总体矩阵如下所示：

M =
    1.0000         0         0
    0.6667    0.3333         0
    0.6667         0    0.3333
    0.3333    0.6667         0
    0.3333    0.3333    0.3333
    0.3333         0    0.6667
         0    1.0000         0
         0    0.6667    0.3333
         0    0.3333    0.6667
         0         0    1.0000

Code:

现在我们来看看生成这一切的 MATLAB 代码： 我使用该功能nmultichoosek from 这个答案 https://stackoverflow.com/a/28284672/3139711 and accumarray实现我们的目标：

function M = possibleMixturesOfNSubstances(N, percentageSteps)
RepCombs = nmultichoosek(1:N, percentageSteps);
numCombs = size(RepCombs,1);
M = accumarray([repmat((1:numCombs).', percentageSteps, 1), RepCombs(:)], 1/percentageSteps, [numCombs, N]);

如果你想要百分比[0, 10, ... 90, 100]并且有 4 种物质，使用以下命令调用此函数possibleMixturesOfNSubstances(4,10)