Как я могу получить «n» возможных матриц из двух векторов?

Question

Я искал алгоритм для решения всех возможных матриц размерности «n», который может быть получен с двумя массивами, одной из сумм строк, а другой - суммой столбцов матрицы , Например, если у меня следующую матрицу размерности 7:

matriz= [ 1 0 0 1 1 1 0 
      1 0 1 0 1 0 0 
      0 0 1 0 1 0 0 
      1 0 0 1 1 0 1 
      0 1 1 0 1 0 1 
      1 1 1 0 0 0 1 
      0 0 1 0 1 0 1 ] 

Сумма столбцов:

Col = [4 2 5 2 6 1 4]

сумма строк являются:

строка = [4 3 2 4 4 4 3]

Теперь я хочу получить все возможные матрицы «единиц и нулей», где сумма столбцов и строк соответствует условию «col» и «row» соответственно.

Буду признателен за идеи, которые могут помочь решить эту проблему.

Answer 1

Одним из очевидных способов является принудительное решение: для первой строки генерируйте все возможности, которые имеют правильную сумму, а затем для каждого из них генерируют все возможности для второй строки и т. Д. После того, как вы сгенерировали все строки, вы проверяете правильность суммы столбцов. Но это займет много времени. Моя математика может быть ржавой в это время дня, но я считаю, что число различных возможностей для ряда длин n, из которых k бит равно 1, задается binomial coefficient или nchoosek(n,k) в Matlab. Для того, чтобы определить общее количество возможностей, вы должны умножить это число для каждой строки:

>> n = 7; 
>> row= [4 3 2 4 4 4 3]; 
>> prod(arrayfun(@(k) nchoosek(n, k), row)) 
ans = 
    3.8604e+10 

Это много возможностей для проверки! То же самое для столбцов дает

>> col= [4 2 5 2 6 1 4]; 
>> prod(arrayfun(@(k) nchoosek(n, k), col)) 
ans = 
    555891525 

По-прежнему большое количество, но «только» фактор 70 меньше.

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

Оптимизированная версия может альтернативно генерировать строки и столбцы и начинаться с тех, для которых число возможностей является самым низким. Я не знаю, есть ли более элегантное решение, чем этот метод грубой силы, мне было бы интересно его услышать.