具有两个非平凡约束的随机二进制矩阵 [英] Random binary matrix with two non-trivial constraints

问题描述

我需要生成一个K列和N行的随机矩阵，其中包含1和0，例如:

I need to generate a random matrix of K columns and N rows containing ones and zeroes, such that:

a)每行恰好包含k个.
b)每一行都彼此不同(组合键表示，如果N> nchoosek(K, k)将会有nchoosek(K,k)行).

a) Each row contains exactly k ones.
b) Each row is different from the other (combinatorics imposes that if N > nchoosek(K, k) there will be nchoosek(K,k) rows).

假设我想要N = 10000(在所有可能的nchoosek(K, k) = 27405组合中)，不同的1×K向量(具有K = 30)包含k(具有k = 4)个零和K - k零.

Assume I want N = 10000 (out of all the possible nchoosek(K, k) = 27405 combinations), different 1×K vectors (with K = 30) containing k (with k = 4) ones and K - k zeroes.

此代码:

clear all; close
N=10000; K=30; k=4;
M=randi([0 1],N,K);
plot(sum(M,2)) % condition a) not satisfied

既不满足a)也不满足b).

does not satisfy neither a) nor b).

此代码:

clear all; close;
N=10000;
NN=N;  K=30; k=4;
tempM=zeros(NN,K);   
for ii=1:NN
ttmodel=tempM(ii,:);
ttmodel(randsample(K,k,false))=1;  %satisfies condition a)
tempM(ii,:)=ttmodel;
end
Check=bi2de(tempM);                    %from binary to decimal
[tresh1,ind,tresh2] = unique(Check);%drop the vectors that appear more than once in the   matrix
M=tempM(ind,:);                             %and satisfies condition b)
plot(sum(M,2))                                  %verify that condition a) is satisfied
%Effective draws, Wanted draws, Number of possible combinations to draw from
[sum(sum(M,2)==k) N nchoosek(K,k) ]  

满足条件a)和部分条件b).我之所以说部分原因是因为除非NN >> N，否则最终矩阵将包含少于N个彼此不同的行.

satisfies condition a) and partially condition b). I say partially because unless NN>>N the final matrix will contain less than N rows each different from each other.

有没有更好，更快的方法(可以避免for循环和需要NN >> N)来解决问题?

Is there a better and faster way (that possible avoids the for cycle and the need of having NN>>N) to solve the problem?

推荐答案

首先，生成一个位置的 N 个唯一的k长排列:

First, generate N unique k-long permutations of the positions of ones:

cols = randperm(K, N);
cols = cols(:, 1:k);

然后生成匹配的行索引:

Then generate the matching row indices:

rows = meshgrid(1:N, 1:k)';

最后使用以下命令创建稀疏矩阵:

and finally create the sparse matrix with:

A = sparse(rows, cols, 1, N, K);

要获取矩阵的完整形式，请使用full(A).

To obtain the full form of the matrix, use full(A).

K = 10;
k = 4;
N = 5;

cols = randperm(K, N);
cols = cols(:, 1:k);
rows = meshgrid(1:N, 1:k)';
A = sparse(rows, cols , 1, N, K);
full(A)

我得到的结果是:

ans = 
    1   1   0   0   0   0   0   1   0   1
    0   0   1   1   0   1   0   0   0   1
    0   0   0   1   1   0   1   0   1   0
    0   1   0   0   0   0   1   0   1   1
    1   1   1   0   0   1   0   0   0   0

即使对于较大的 K 和 N 值，此计算也应该非常快.对于 K = 30， k = 4， N = 10000，在不到0.01秒的时间内即可获得结果.

This computation should be pretty fast even for large values of K and N. For K = 30, k = 4, N = 10000 the result was obtained in less than 0.01 seconds.

这篇关于具有两个非平凡约束的随机二进制矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！