Поиск всех комбинаций нескольких переменных, суммирующих до 1

Question

Я пытаюсь решить уравнение

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).

Затем я ищу все записи в результирующем массиве, которые равны единице. Код (показанный ниже для дальнейшего пояснения) работает нормально и был протестирован для 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) в mat(11,1)от максимального значения x1 до максимального значения x2,

Для трехмерной матрицы все записи удовлетворяют условию, лежащему на диагональной плоскости через mat(1,1,11), mat(1,11,1), mat(11,1,1)от максимального значения x1 а также x2 до максимального значения x3,

То же самое верно для более высоких измерений: все интересующие матричные элементы лежат на n-1 размерная гиперплоскость зафиксирована на наибольшем значении оси в каждом измерении.

---

Вопрос: есть ли способ напрямую определить индексы элементов на этих n-1 размерная гиперплоскость? Если это так, вся проблема может быть решена за один шаг без необходимости вычисления всех элементов n-мерной матрицы и последующего поиска элементов, представляющих интерес.

Answer 1

Математика:

Вместо того, чтобы идти по гиперкубу, мы решаем уравнение

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],

Мы можем построить биекцию между этим и комбинаторной концепцией комбинаций с повторением.

Статья в Википедии даже косвенно упоминает основную биекцию утверждением:

Число мультиподмножеств размера 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

Код:

А теперь для кода MATLAB, который генерирует все это: я использую функцию nmultichoosek из этого ответа и 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)