如何生成具有特定模式的二进制矩阵? [英] How can I generate a binary matrix with specific patterns?

问题描述

我有一个n×n大小的二进制矩阵.下面给出的是一个示例二进制矩阵(实际矩阵要大得多):

1010001
1011011
1111000
0100100

给定p = m * n，我有2 ^ p种可能的矩阵配置.我想获得一些满足某些规则的模式.例如:

1. 我希望第j列中的不少于k个单元格为零
2. 我希望第i行的单元格值之和大于给定的数字Ai
3. 我希望一列中至少连续有g个单元格
4. 等...

如何在不顺序检查所有2 ^ p组合的情况下严格满足这些约束的模式?

在我的情况下，p可以是2400之类的数字，给出大约2.96476e + 722的可能组合.

解决方案

不是迭代所有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(使用函数 RANDPERM 函数对矢量进行随机重新排序生成随机索引顺序.使用检测到序列在0和1之间切换的边缘. DIFF 功能.然后使用边缘的索引查找最长的序列的长度(使用查找和 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

此代码将循环运行，直到所有行总和都大于或等于我们想要的最小总和.首先，使用 解决方案

Instead of iterating over all 2^p combinations, one way you could generate such binary matrices is by performing repeated row- and column-wise operations based on the given constraints you have. As an example, I'll post some code that will generate a matrix based on the three constraints you have listed above:

• A minimum number of zeroes per column
• A minimum sum for each row
• A minimum sequential length of ones per column

Initializations:

First start by initializing a few parameters:

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)

Helper functions:

Next, create a couple of functions for generating column vectors that match constraints 1 and 3 from above:

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

The function make_column will first create a logical column vector with the minimum number of 0 elements and the remaining elements set to 1 (using the functions TRUE and FALSE). This vector will undergo random reordering of its elements until it contains a sequence of ones greater than or equal to the desired minimum length of ones. This is done using the randomize_column function. The vector is randomly reordered using the RANDPERM function to generate a random index order. The edges where the sequence switches between 0 and 1 are detected using the DIFF function. The indices of the edges are then used to find the length of the longest sequence of ones (using FIND and MAX).

Generate matrix columns:

With the above two functions we can now generate an initial binary matrix that will at least satisfy constraints 1 and 3:

binMat = false(nRows,nColumns);  % Initialize matrix
for iColumn = 1:nColumns,
  binMat(:,iColumn) = make_column;  % Create each column
end

Satisfy the row sum constraint:

Of course, now we have to ensure that constraint 2 is satisfied. We can sum across each row using the SUM function:

rowSum = sum(binMat,2);

If any elements of rowSum are less than the minimum row sum we want, we will have to adjust some column values to compensate. There are a number of different ways you could go about modifying column values. I'll give one example here:

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

This code will loop until all the row sums are greater than or equal to the minimum sum we want. First, the index of the row with the smallest sum (rowIndex) is found using MIN. Next, the indices of the zeroes in that row are found and one of them is randomly chosen as the index of a column to modify (columnIndex). Using make_column, a new column vector is continuously generated until the 0 in the given row becomes a 1. That column in the binary matrix is then updated and the new row sum is computed.

Summary:

For a relatively small 10-by-10 binary matrix, and the given constraints, the above code usually completes in no more than a few seconds. With more constraints, things will of course get more complicated. Depending on how you choose your constraints, there may be no possible solution (for example, setting minRowSum to 6 will cause the above code to never converge to a solution).

Hopefully this will give you a starting point to begin generating the sorts of matrices you want using vectorized operations.

这篇关于如何生成具有特定模式的二进制矩阵?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！