How can I generate an array of binary data of this form?

6 ビュー (過去 30 日間)
Luqman Saleem
Luqman Saleem 2019 年 2 月 14 日
コメント済み: Stephen23 2019 年 2 月 19 日
The N is input.
I want to write a code which gives array of dimension (combin X N) where combin is all possible combination such that sum of each row is N/2.
Confusion? Let me explain with an example...
Let N = 4, I want output array of the following form
[0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0]
note that the sum of each row if N/2 = 2. Let's see another example...
if N=6, output should be
[0 0 0 1 1 1
0 0 1 0 1 1
0 0 1 1 0 1
0 0 1 1 1 0
0 1 0 0 1 1
0 1 0 1 0 1
..... so on...]
I have a code but it is very inefficient (and also it does not work for N>18 (also it's very slow)
A = dec2bin( 1:2^N-1)-'0';
required_array = A(sum(A,2)==N/2,:);
  1 件のコメント
Stephen23
Stephen23 2019 年 2 月 19 日
"I want to write a code which gives array of dimension (combin X N) where combin is all possible combination such that sum of each row is N/2."
Note that what your examples show are permutations, not combinations.
The difference is simple:
  • If the order doesn't matter, it is a Combination.
  • If the order does matter it is a Permutation (like in your examples).

サインインしてコメントする。

採用された回答

Stephen23
Stephen23 2019 年 2 月 15 日
編集済み: Stephen23 2019 年 2 月 15 日
It might not be the most beautiful algorithm in the world, but this works (on 64 bit MATLAB) for even N values up to at least
  • N = 20, giving 184756 rows in 15 seconds
  • N = 22, giving 705432 rows in 106 seconds.
  • N = higher might be possible, if you are patient enough and have enough memory...
but keep in mind that at some point you will simply run out of memory.
It is easy to check that all rows sum to the requested value. In contrast there is no obvious way to check if any rows are missing, but I did notice that the number of rows matches exactly with OEIS A000984, which might have some relevance.
N = 12;
M = [0,1;1,0];
for k = 3:N
R = size(M,1);
M = [zeros(R,1),M;ones(R,1),M;M,zeros(R,1);M,ones(R,1)];
M = unique(M(sum(M,2)<=N/2,:),'rows');
end
M = M(sum(M,2)==N/2,:);
For N=12 this gives:
>> size(M)
ans =
924 12
>> M
ans =
0 0 0 0 0 0 1 1 1 1 1 1
0 0 0 0 0 1 0 1 1 1 1 1
0 0 0 0 0 1 1 0 1 1 1 1
0 0 0 0 0 1 1 1 0 1 1 1
0 0 0 0 0 1 1 1 1 0 1 1
0 0 0 0 0 1 1 1 1 1 0 1
0 0 0 0 0 1 1 1 1 1 1 0
0 0 0 0 1 0 0 1 1 1 1 1
0 0 0 0 1 0 1 0 1 1 1 1
... lots of rows here
1 1 1 1 0 1 0 0 1 0 0 0
1 1 1 1 0 1 0 1 0 0 0 0
1 1 1 1 0 1 1 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0 0 1
1 1 1 1 1 0 0 0 0 0 1 0
1 1 1 1 1 0 0 0 0 1 0 0
1 1 1 1 1 0 0 0 1 0 0 0
1 1 1 1 1 0 0 1 0 0 0 0
1 1 1 1 1 0 1 0 0 0 0 0
1 1 1 1 1 1 0 0 0 0 0 0
PS: of course recursive algorithms for generating permutations are simple but when I tried some with added short-circuit behavior for repeated rows, they were significantly slower than the above loop.

その他の回答 (2 件)

Kevin Phung
Kevin Phung 2019 年 2 月 14 日
編集済み: Kevin Phung 2019 年 2 月 14 日
N = 18;
M = zeros(N); %preallocate space
for i =1: size(M,1)
ind = randperm(N); % generates random indices between 1:N
M(i,ind(1:N/2)) = 1; %grab half of those indices, turn M at those indices to 1
end
M
let me know if this helps
  1 件のコメント
Luqman Saleem
Luqman Saleem 2019 年 2 月 18 日
very helpful, thank you.

サインインしてコメントする。


Luna
Luna 2019 年 2 月 14 日
編集済み: Luna 2019 年 2 月 14 日
Hi Luqman,
Please see the code below and read the comments:
N = 6;
permutatedArray = [ones(1,N/2),zeros(1,N/2)]; % this creates a [1 1 1 0 0 0] row vector.
result = logical(unique(perms(permutatedArray),'rows')); % this is the result with uniques of all.
% if combinNumber equals rowNumber we did the right thing just for checking:
combinNumber = nchoosek(N,N/2)
rowNumber = size(result,1)
  1 件のコメント
Luqman Saleem
Luqman Saleem 2019 年 2 月 14 日
Hey Luna,
Thank you for your time.
your code does not work for small N but unfortunetly, it can not compute the required array for N>10

サインインしてコメントする。

カテゴリ

Help Center および File ExchangeMatrices and Arrays についてさらに検索

製品


リリース

R2018b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by