1

I want to generate a binary matrix, let say (8,1). with equal probability means four 1's and four 0s in a matrix. with different permutation of these elements total 70 combination are possible (e.g 8C4). I want these all possible combination one by one. please help.

user2767151
  • 11
  • 1

2 Answers2

1

The straighforward answer is:

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

or in a fancier form:

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

where N is the length of your vector (N = 8 in your example). However, expect this solution to be very slow for large arrays.

Surprisingly, in this case a faster method is to generate all possible permutations (see here) and eliminate those that do not satisfy the desired criterion:

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

Benchmark

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

The results I got were:

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

... and for N = 10:

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

Not only that nchoosek fails for large values of N, it's also slower.

Community
  • 1
  • 1
Eitan T
  • 32,660
  • 14
  • 72
  • 109
0

Here is an even faster way to do it, using the fact that you are looking for a subset of binary number representations:

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

The performance comparison:

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

Gives these timings:

Elapsed time is 0.002200 seconds.
Elapsed time is 0.594309 seconds.

Note that the resulting lines will be in different orders for both solutions.

Dennis Jaheruddin
  • 21,208
  • 8
  • 66
  • 122