Вместо итерации по всем 2 ^ p комбинациям одним из способов создания таких двоичных матриц является выполнение повторяющихся операций со строками и столбцами на основе имеющихся у вас заданных ограничений. В качестве примера я опубликую некоторый код, который будет генерировать матрицу на основе трех ограничений, перечисленных выше:
- Минимальное количество нулей на столбец
- Минимальная сумма для каждой строки
- Минимальная последовательная длина единиц на столбец
инициализация:
Сначала запустите инициализацию нескольких параметров:
nRows = 10; % Row size of matrix
nColumns = 10; % Column size of matrix
minZeroes = 5; % Constraint 1 (for columns)
minRowSum = 5; % Constraint 2 (for rows)
minLengthOnes = 3; % Constraint 3 (for columns)
Вспомогательные функции:
Затем создайте пару функций для генерации векторов столбцов, которые соответствуют ограничениям 1 и 3 сверху:
function vector = make_column
vector = [false(minZeroes,1); true(nRows-minZeroes,1)]; % Create vector
[vector,maxLength] = randomize_column(vector); % Randomize order
while maxLength < minLengthOnes, % Loop while constraint 3 is not met
[vector,maxLength] = randomize_column(vector); % Randomize order
end
end
function [vector,maxLength] = randomize_column(vector)
vector = vector(randperm(nRows)); % Randomize order
edges = diff([false; vector; false]); % Find rising and falling edges
maxLength = max(find(edges == -1)-find(edges == 1)); % Find longest
% sequence of ones
end
Функция make_column сначала создает вектор логического столбца с минимальным количеством элементов 0, а остальные элементы равны 1 (с использованием функций TRUE и FALSE ). Этот вектор будет подвергаться случайному переупорядочению своих элементов, пока он не будет содержать последовательность единиц, большую или равную требуемой минимальной длине единиц. Это делается с помощью функции randomize_column . Вектор случайным образом переупорядочивается с использованием функции RANDPERM для генерации случайного порядка индексов. Края, где последовательность переключается между 0 и 1, определяются с помощью функции DIFF . Индексы ребер затем используются, чтобы найти длину самой длинной последовательности единиц (используя FIND и MAX ).
Создание столбцов матрицы:
Используя две вышеупомянутые функции, мы можем теперь сгенерировать начальную двоичную матрицу, которая будет по крайней мере удовлетворять ограничениям 1 и 3:
binMat = false(nRows,nColumns); % Initialize matrix
for iColumn = 1:nColumns,
binMat(:,iColumn) = make_column; % Create each column
end
Удовлетворить ограничение суммы строк:
Конечно, теперь мы должны убедиться, что ограничение 2 выполнено. Мы можем суммировать по каждой строке, используя функцию SUM :
rowSum = sum(binMat,2);
Если какие-либо элементы rowSum меньше минимальной суммы строки, которую мы хотим, нам придется скорректировать некоторые значения столбца, чтобы компенсировать это. Существует несколько способов изменить значения столбцов. Я приведу один пример здесь:
while any(rowSum < minRowSum), % Loop while constraint 2 is not met
[minValue,rowIndex] = min(rowSum); % Find row with lowest sum
zeroIndex = find(~binMat(rowIndex,:)); % Find zeroes in that row
randIndex = round(1+rand.*(numel(zeroIndex)-1));
columnIndex = zeroIndex(randIndex); % Choose a zero at random
column = binMat(:,columnIndex);
while ~column(rowIndex), % Loop until zero changes to one
column = make_column; % Make new column vector
end
binMat(:,columnIndex) = column; % Update binary matrix
rowSum = sum(binMat,2); % Update row sum vector
end
Этот код будет повторяться до тех пор, пока все суммы строк не станут больше или равны минимальной сумме, которую мы хотим. Во-первых, индекс строки с наименьшей суммой ( rowIndex ) определяется с использованием MIN . Затем, индексы нулей в этой строке находятся, и один из них выбирается случайным образом в качестве индекса столбца для изменения ( columnIndex ). Используя make_column , новый вектор столбца непрерывно генерируется, пока 0 в данной строке не станет 1. Этот столбец в двоичной матрице затем обновляется и вычисляется сумма новой строки.
Резюме:
Для сравнительно небольшой двоичной матрицы 10 на 10 и заданных ограничений приведенный выше код обычно завершается не более чем за несколько секунд. С большим количеством ограничений, конечно, все будет сложнее. В зависимости от того, как вы выбираете свои ограничения, возможное решение может быть не найдено (например, установка minRowSum на 6 приведет к тому, что приведенный выше код никогда не сойдет к решению).
Надеемся, что это даст вам отправную точку для начала генерации типов матриц, которые вы хотите, используя векторизованные операции.