Specified number of ones in the matrix (column and row)

11 次查看（过去 30 天）
Darek Myszk
Darek Myszk 2018-10-26
编辑： Bruno Luong 2018-12-2
Hi. I need to create a square matrix filled with random values of 1 and 0. Sum of each row and each column must be equal to the given condition. e.g. matrix: 5x5 ; sum of 1's: 3

请先登录，再回答此问题。

采纳的回答

Bruno Luong
Bruno Luong 2018-10-26
编辑：Bruno Luong 2018-10-26
I couldn't figure out how to generate k permutations that are not redundant beside test and discard until it meets the condition (technique that I really hate to use). So here is the code that does what you want but I'm far from proud of it:
n = 10; % Matrix dimension
k = 4; % row/column sum target of 1s
l = min(k,n-k);
J = zeros(n,l);
for i=1:l
while true
J(:,i) = randperm(n);
if all(all(J(:,i)-J(:,1:i-1)~=0,2),1)
break
end
end
end
I = repmat((1:n)',1,l);
A = accumarray([I(:) J(:)],1,[n n]);
if l < k
A = 1-A;
end
sum(A,1)
sum(A,2)
  4 个评论
显示 2更早的评论
Bruno Luong
Bruno Luong 2018-12-2
The idea is to iterate for 1:k, each iteration I place one 1 for each row and column randomly.
This is carried out by
randperm(n)
which decides which column of 1s for respectively row = 1,...n (set by I).
If I do the oterative process k time then the sum(A,2) will be k.
However sum(A,1)<=k, and it is stritly <k if and only if two permulations get the same values.
So to ensure sum(A,1)==k as required, I need to make sure the new generate permutation does not have the same value with all preceding generated. This is the role of the while loop with the test all(all(J(:,i)-J(:,1:i-1)~=0,2),1).
The accumarray put everything together in A according to row/colums generated.
The trick
l = min(k,n-k);
...
if l < k
A = 1-A;
end
is to swap the role of 0 and 1, so that I can work on the least random positions to generate.
Bruno Luong
Bruno Luong 2018-12-2
编辑：Bruno Luong 2018-12-2
I provide a much better method (without rejection) below, according to the idea of Akira Agata

请先登录，再进行评论。

更多回答（3 个）

Bruno Luong
Bruno Luong 2018-12-2
编辑：Bruno Luong 2018-12-2
From an idea by Akira Agata
n = 10; % Matrix dimension
k = 4; % row/column sum target of 1s
r = [ones(1,k) zeros(1,n-k)];
c = circshift(r,-k+1);
A = toeplitz(c,r);
A = A(randperm(n),randperm(n))
sum(A,2)
sum(A,1)
  2 个评论
Darek Myszk
Darek Myszk 2018-12-2
Its looks very good, but next question.
Created matrix A, I put in genmat = [ I A' ], and why, when I put all this code in the loop, always minimum distance of linear block code is the same value? Using the previous script, value of minimum distance was different, depending on the iteration.
___
command to check minimum distance: wt = gfweight(genmat).
I is eye's submatrix.
Bruno Luong
Bruno Luong 2018-12-2
编辑：Bruno Luong 2018-12-2
I'm not sure I understand with verbal description, minimum distance of what? What is inear block code?
Edit: I see you mention some function that seems to be in Communication Toolbox. I'm not familiar with it or the goal you want to achieve.
It might be possible that this method of toeplitz matrix is not completely random. I do not put too much though on it.

请先登录，再进行评论。

John D'Errico
John D'Errico 2018-10-26
编辑：John D'Errico 2018-10-26
Just a quick guess...
This reduces to finding a set of 3 permutations of the numbers 1:5, such that none of them fall in the same place. So we might consider the set defined by:
p =
3 4 5 2 1
4 2 1 3 5
1 3 2 5 4
Now, create your matrix as:
M = eye(5);
M = M(:,p(1,:)) + M(:,p(2,:))+ M(:,p(3,:))
M =
1 0 1 0 1
0 1 1 1 0
1 1 0 1 0
1 1 0 0 1
0 0 1 1 1
So sort of like derangements, but not really. You could actually create M using a more efficient expression, thus with accumarray or sparse, but the way I wrote it may be more intuitively understandable.
Given all that, can you find the array p in a simple way? I can think of at least one simple way.
allperms = perms(1:5);
p = nan(3,5);
for i = 1:3
k = randi(size(allperms,1));
p(i,:) = allperms(k,:);
allperms(any(allperms == p(i,:),2),:) = [];
end
which yields:
p
p =
3 2 1 4 5
5 1 4 3 2
4 3 5 2 1
Note: the above will be problematic if you try to solve the problem for large matrices, since perms will explode. But you did ask for 5x5.
  3 个评论
显示 1更早的评论
Bruno Luong
Bruno Luong 2018-10-26
编辑：Bruno Luong 2018-10-26
John: If I'm not mistaken, to makes it works the 3 permutations must give different values at the same index.
John D'Errico
John D'Errico 2018-10-26
Yes. Each permutation must be distinct from the others at each location.
As fas as getting a different permutation? That is trivial. As long as you do not reset the random seed before each time through, then randi will give you a different set.
For example, I just re-ran it.
p
p =
2 3 5 4 1
3 2 1 5 4
4 1 2 3 5
Which corresponds to the matrix:
M =
0 1 1 0 1
1 1 1 0 0
1 1 0 1 0
1 0 0 1 1
0 0 1 1 1

请先登录，再进行评论。

Darek Myszk
Darek Myszk 2018-10-26
Matrix 5x5, and limit of'1s in the subject is an example. Size of matrix, and limit must be given at start of the program :/

类别

在 Help Center 和 File Exchange 中查找有关 Matrices and Arrays 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by