查找多个加起来为1的变量的所有组合 [英] Finding all combinations of multiple variables summing to 1
问题描述
我正在尝试求解方程式
x1 + x2 + x3 + .... + xn = 1
其中所有 xi 的值都限制为 [0，0.1，0.2，...，0.9，1] .
where the values of all xi are restricted to [0, 0.1, 0.2, ..., 0.9, 1].
当前，我通过首先生成一个n维数组 mat 来解决该问题，其中每个元素位置的值都是轴值的总和，轴值之和在 axisValues =0:0.1:1 :
Currently, I am solving the problem by first generating an n-dimensional array mat, where at each element location the value is the sum of the axis values, which vary in axisValues = 0:0.1:1:
mat(i,j,k,...,q) = axisValues(i) + axisValues(j) + ... + axisValues(q).
然后，我搜索结果数组中等于1的所有条目.该代码(如下所示以作进一步说明)工作正常，并且已针对多达5个维度进行了测试.问题是，运行时间呈指数增长，并且我需要脚本在多个维度上工作.
Then I search for all entries of the resulting array that are equal to one. The code (shown below for further clarification) is working fine and has been tested for up to 5 dimensions. The problem is, that the run time increases exponentially and I need the script to work for more than a few dimensions.
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.
我觉得使用问题对称性的以下想法可能有助于显着减少计算时间:
I have the feeling that the following idea using the symmetry of the problem might help to significantly reduce calculation time:
对于2D矩阵，所有满足以上条件的条目都位于 mat(1,11)到 mat(11,1)的对角线上，即 x1 的最大值到 x2 的最大值.
For a 2D matrix, all entries that fulfill the condition above lie on the diagonal from mat(1,11) to mat(11,1), i.e. from the maximal value of x1 to the maximal value of x2.
对于3D矩阵，所有条目都通过 mat(1,1,11)， mat(1,11,1)， mat(11,1,1)，即从 x1 和 x2 的最大值到 x3的最大值.
For a 3D Matrix, all entries fulfill the condition that lie on a diagonal plane through mat(1,1,11), mat(1,11,1), mat(11,1,1), i.e. from the maximal value of x1 and x2 to the maximal value of x3.
对于更高的维度也是如此:所有感兴趣的矩阵元素都位于一个 n-1 个维度超平面上，该超平面固定在每个维度的最高轴值上.
The same is true for higher dimensions: All matrix elements of interest lie on an n-1 dimensional hyper-plane fixed on the highest axis value in each dimension.
问题是:是否有一种方法可以直接确定这些 n-1 维超平面上元素的索引?如果是这样，则整个问题可以一步解决，而无需计算n维矩阵的所有条目，然后搜索感兴趣的条目.
The question is: Is there a way to directly determine the indices of the elements on these n-1 dimensional hyper-plane? If so, the whole problem could be solved in one step and without needing to calculate all entries of the n-dimensional matrix and then searching for the entries of interest.
推荐答案
数学:
我们不用方程式，而是求解方程式
Math:
Instead of going the hypercube-way, we solve the equation
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 对应于双色子方程
where each x(i) can vary in [0, 1/k, 2/k, ... (k-1)/k, 1] instead. In your case k will be 10, as this will then result in the percentages [0, 10, 20, ... 90, 100].
Multiplied by k this corresponds to the diophantine equation
x(1) + x(2) + ... + x(n) = k,
其中所有 x(i)均以 [0，1，2，... k-1，k] 改变.
我们可以在此与 具有重复的组合 .
We can build a bijection between this and the combinatorial concept of combinations with repetition.
维基百科文章甚至通过以下语句隐式提及了潜在的双射:
The wikipedia article even implicitly mentions the underlying bijection by the statement:
大小为k的多子集的数量为Diophantine方程
x1 + x2 + ... + xn = k的非负整数解的数量.
举个小例子，假设我们要使用 k = 3 和百分号为 [0，33，66，100] .给定集合 {1,2,3} 的所有k个多重组合:
For a smaller example, say we are going with k=3 and percentages in [0, 33, 66, 100] instead. Given all k-multicombinations of the set {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 添加到相应的Matrix条目 M(i，j).第一行将对应于 [1/3 + 1/3 + 1/3，0，0] = [1,0,0] .此过程生成的总体矩阵如下所示:
Then we map these to your percentages using the following rule:
For every row i, if the entry is j, then add 1/3 of the percentage to the corresponding Matrix entry M(i,j). The first row will correspond to [1/3 + 1/3 + 1/3, 0, 0] = [1,0,0].
The overall matrix generated by this process will look like this:
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
代码:
现在，对于生成所有这些的MATLAB代码:我使用来自此答案和 accumarray 的函数 nmultichoosek 来完成我们的目标:
Code:
And now for the MATLAB code that generates all this:
I use the function nmultichoosek from this answer and accumarray to accomplish our goal:
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)
If you want percentages in [0, 10, ... 90, 100] and have 4 substances, call this function using possibleMixturesOfNSubstances(4,10)
这篇关于查找多个加起来为1的变量的所有组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
