matlab - 具有两个非平凡约束的随机二元矩阵

Question

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

a) 每行恰好包含 k的。
b) 每行都与其他行不同(组合学规定，如果 N > nchoosek(K, k) 将有 nchoosek(K,k) 行)。

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

这段代码:

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)。

这段代码:

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每行彼此不同。

是否有更好更快的方法(可能避免 for 循环以及需要 NN>>N)来解决问题？

Answer 1

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

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

然后生成匹配的行索引:

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

最后创建稀疏矩阵:

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

要获取矩阵的完整形式，请使用 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 秒内获得。