Оптимизировать алгоритм, который генерирует количество единиц в каждом двоичном состоянии

Question

TL; DR : мне нужно найти все возможные комбинации N векторов строк (размером 1xB), чья сумма по строкам дает желаемый вектор результата (также размера * 1005) *).

---

У меня есть двоичная матрица (только 1 или 0 записей) размером N x B, где N обозначает количество единиц, а B обозначает количество ячеек. Каждая единица, то есть каждая строка матрицы может находиться в одном из 2 ^ B состояний. То есть, если B = 2, возможны следующие состояния: {0,0}, {0,1}, {1,0} или {1,1}. Если B = 3, то возможные состояния: {0,0,0}, {0,0,1}, {0,1,0}, {0,1,1}, {1,0,0}, {1,0,1}, {1,1,0} или {1,1,1}. В основном двоичное представление чисел от 0 до 2 ^ B-1.

Для матрицы я знаю сумму по строкам матрицы, например, {1,2}. Эта сумма может быть достигнута с помощью различных двоичных матриц, таких как [0,0;0,1;1,1] или [0,1;0,1;1,0]. Количество единиц в каждом состоянии составляет {1,1,0,1} и {0,2,1,0} соответственно для каждой из матриц, где первое число соответствует первому состоянию {0,0}, второй ко второму состоянию {0,1} и так далее в порядке возрастания. Моя задача состоит в том, чтобы найти все возможные векторы этих чисел состояний, которые удовлетворяют определенной матричной сумме.

Теперь, чтобы реализовать это в MATLAB, я использовал рекурсию и глобальную переменную. Для меня это был самый простой подход, однако, он занимает много времени. Код, который я использовал, приведен ниже:

function output = getallstate()
   global nState % stores all the possible vectors
   global nStateRow % stores the current row of the vector
   global statebin %stores the binary representation of all the possible states
   nState = [];
   nStateRow = 1;
   nBin = 2; % number of columns or B
   v = [1 2]; % should always be of the size 1 x nBin
   N = 3; % number of units
   statebin = de2bi(0:(2 ^ nBin - 1), nBin) == 1; % stored as logical because I use it to index later
   getnstate(v, 2 ^ nBin - 1, nBin) % the main function
   checkresult(v, nState, nBin) % will result in false if even one of the results is incorrect
   % adjust for max number of units, because the total of each row cannot exceed this number.
   output = nState(1:end-1, :); % last row is always repeated (needs to be fixed somehow)
   output(:, 1) = N - sum(output(:, 2:end), 2); % the first column, that is the number of units in the all 0 state is always determined by the number of units in the other states
   if any(output(:, 1) < 0)
      output(output(:, 1) < 0, :) = [];
   end
end

function getnstate(r, state, nBin)
   global nState
   global nStateRow
   global statebin

   if state == 0
      if all(r == 0)
         nStateRow = nStateRow + 1;
         nState(nStateRow, :) = nState(nStateRow - 1, :);
      end
   else
      for a = 0:min(r(statebin(state + 1, :)))
         nState(nStateRow, state + 1) = a;
         getnstate(r - a * statebin(state + 1, :), state - 1, nBin);
      end
   end
end

function allOk = checkresult(r, nState, nBin)
   % just a function that checks whether the obtained vectors all result in the correct sum
   allstate = de2bi(0:(2 ^ nBin - 1), nBin);
   allOk = true;
   for iRow = 1:size(nState, 1)
      sumR = sum(bsxfun(@times, allstate, nState(iRow, :).'), 1);
      allOk = allOk & isequal(sumR,r);
   end
end

function b = de2bi(d, n)
d = d(:);
[~, e] = log2(max(d));
b = rem(floor(d * pow2(1-max(n, e):0)), 2);
end

Приведенный выше код работает нормально и выдает все возможные состояния, но, как и ожидалось, он становится медленнее по мере увеличения количества столбцов (B) и количества единиц (N). Кроме того, он использует глобалы. Вот мои вопросы:

1. Есть ли способ генерировать их без использования глобалов?
2. Существует ли нерекурсивный способ для этого алгоритма?

РЕДАКТИРОВАТЬ 1

3. Каким образом все вышеперечисленное имеет оптимизированный алгоритм, который работает быстрее, чем текущая версия?

РЕДАКТИРОВАТЬ 2

Добавлена ​​функция de2bi для удаления зависимости от Communications Toolbox.