2

我需要生成包含一和零的K列和N行的随机矩阵，例如：

a）每一行都包含k一个。
b) 每一行都与其他行不同（组合学规定如果N>nchoosek(K, k)就会有nchoosek(K,k)行）。

假设我想要N = 10000（在所有可能的nchoosek(K, k) = 27405组合中），不同的 1×K 向量（with K = 30）包含 k 个（with 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）来解决问题？

4

3 回答 3

2

首先，生成一个位置的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 秒的时间内获得了结果。

于 2013-06-23T08:23:31.433 回答
0

您可以使用 randperm(n) 生成从 1 到 n 的随机整数序列，并将非重复序列作为行存储在矩阵 M 中，直到 size(unique(M,'rows'),1)==size(M,1 ）。然后，您可以使用 M 来索引逻辑矩阵，每行中具有适当数量的真值。

于 2013-06-23T04:57:18.283 回答
0

如果您有足够的内存用于 nchoosek(K,k) 整数，则构建一个数组，使用部分 Fisher-Yates 洗牌来获得其中 N 个适当的均匀随机子集。现在，给定 N 个整数的数组，将每个整数解释为代表最终数组每一行的组合的等级。如果你使用colexicographical ordering的组合，从一个等级计算组合非常简单（尽管它使用了很多二项式组合函数，所以有一个快速的组合是值得的）。

我不是 Matlab 人，但我在 C 中做过类似的事情。这段代码，例如：

for (i = k; i >= 1; --i) {
    while ((b = binomial(n, i)) > r) --n;
    buf[i-1] = n;
    r -= b;
}

buf[]将使用索引 from 0to填充数组，n-1用于按 colex 顺序排列的元素的r第 th 个组合。您会将这些解释为s 在您的行中的位置。kn1

于 2013-06-23T06:24:35.693 回答