2

次のように、1 と 0 を含むK列と行のランダムな行列を生成する必要があります。N

a) 各行には正確に 1 が含まれkます。
b) 各行は他の行とは異なります (組み合わせ論では、N>行nchoosek(K, k)がある場合に課せられnchoosek(K,k)ます)。

N = 10000(すべての可能な組み合わせのうち) k 個 ( ) の 1 と0を含むnchoosek(K, k) = 27405異なる 1×K ベクトル ( ) が必要であると仮定します。K = 30k = 4K - 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) を満たします。NNN>>N でない限り、最終的な行列に含まれる行が互いに異なる行よりも少ないため、部分的に言います。

問題を解決するためのより良い、より高速な方法 (for サイクルと NN>>N の必要性を回避する可能性がある) はありますか?

4

3 に答える 3

2

最初に、1の位置のN 個の一意の k-long 順列を生成します。

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

nchoosek(K,k) 整数に十分なメモリがある場合は、それらの配列を構築し、部分的なフィッシャー イェーツ シャッフルを使用して、それらの N の適切な一様ランダム サブセットを取得します。ここで、N 個の整数の配列が与えられた場合、それぞれを最終的な配列の各行を表す組み合わせのランクとして解釈します。組み合わせの列記順序を使用する場合、ランクから組み合わせを計算するのは非常に簡単です (ただし、多くの二項組み合わせ関数を使用するため、高速な関数を使用する価値があります)。

私は Matlab の専門家ではありませんが、これと似たようなことを C で行ったことがあります。このコードは、たとえば次のとおりです。

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

要素の th番目の組み合わせについて、配列を から のインデックスで埋めますbuf[]。これらは、行内の の位置として解釈します。0n-1rkn1

于 2013-06-23T06:24:35.693 に答える
0

randperm(n) を使用して、1 から n までの整数のランダムなシーケンスを生成し、サイズ (unique(M,'rows'),1)==size(M,1) になるまで、繰り返されないシーケンスを行列 M の行として格納できます。 ）。次に、M を使用して、各行に適切な数の真の値を持つ論理行列にインデックスを付けることができます。

于 2013-06-23T04:57:18.283 に答える