1

たとえば、(8,1) などのバイナリ マトリックスを生成します。確率が等しいとは、マトリックス内に 4 つの 1 と 4 つの 0 があることを意味します。これらの要素の異なる順列により、合計 70 の組み合わせが可能です (例: 8C4)。私はこれらすべての可能な組み合わせを1つずつ望んでいます。助けてください。

4

2 に答える 2

1

簡単な答えは次のとおりです。

unique(perms([true(1, N / 2), false(1, N / 2)]), 'rows')

またはより洗練された形式で：

unique(perms(sparse(1, 1:N / 2, true, 1, N)), 'rows')

Nベクトルの長さはどこにありますか（N = 8あなたの例では）。ただし、このソリューションは大規模な配列では非常に遅くなることが予想されます。

驚くべきことに、この場合、可能な順列をすべて生成し (ここを参照)、目的の基準を満たさない順列を削除する方が高速です。

C = cell(N, 1);                 %// Preallocate memory
[C{:}] = ndgrid([true, false]); %// Generate N grids of binary values
p = cellfun(@(x){x(:)}, C);     %// Convert grids to column vectors
p = [p{:}];                     %// Obtain all combinations
p = p(sum(p, 2) == N / 2, :);   %// Keep only desired combinations

基準

N = 8;

%// Method #1 (one-liner)
tic
for k = 1:1e3
    p = unique(perms(sparse(1, 1:N / 2, true, 1, N)), 'rows');
end
toc

%// Method #2
tic
for k = 1:1e3
    C = cell(N, 1);
    [C{:}] = ndgrid([true, false]);
    p = cellfun(@(x){x(:)}, C);
    p = [p{:}];
    p = p(sum(p, 2) == N / 2, :);
end
toc

私が得た結果は次のとおりです。

Elapsed time is 0.858539 seconds. %// Method #1
Elapsed time is 0.803826 seconds. %// Method #2

...そしてのためにN = 10：

Elapsed time is 55.3068 seconds.  %// Method #1
Elapsed time is 1.03664 seconds.  %// Method #2

nchoosekの値が大きい場合に失敗するだけでなく、N速度も遅くなります。

于 2013-09-15T18:20:50.963 に答える