matlab - matlab中1和0等概率的所有组合的二进制矩阵

Question

我想生成一个二进制矩阵，比如说（8,1）。等概率表示矩阵中有四个 1 和四个 0。通过这些元素的不同排列，总共有 70 种组合是可能的（例如 8C4）。我想要这些所有可能的组合一一。请帮忙。

Answer 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，而且速度也较慢。

Answer 2

这是一种更快的方法，使用您正在寻找二进制数表示的子集的事实：

b = dec2bin(1:2^N-1);
x =  b-'0';
x = x(sum(x,2)==N/2,:);

性能对比：

N = 8;

% Dennis solution
tic
b = dec2bin(1:2^N-1);
x =  b-'0';
x=x(sum(x,2)==N/2,:);
toc

% Eitan 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.002200 seconds.
Elapsed time is 0.594309 seconds.

请注意，两种解决方案的结果行的顺序不同。