Given two numbers n and s, build an n-by-n logical matrix (of only zeros and ones), such that both the row sums and the column sums are all equal to s. Additionally, the main diagonal must be all zeros.
You can assume that: 0 < s < n
Example:
Take n=10 and s=3, here is a possible solution
M =
0 1 0 0 1 1 0 0 0 0
0 0 1 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0 1 0
0 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 1 0 1 0
0 1 1 0 0 0 0 1 0 0
1 0 0 1 0 0 0 0 0 1
0 0 0 1 0 0 0 0 1 1
1 1 0 0 0 0 0 1 0 0
0 0 1 1 0 0 1 0 0 0
Note that the following conditions are all true:
all(sum(M,1)==3) % column sums equal to s all(sum(M,2)==3) % row sums equal to s all(diag(M)==0) % zeros on the diagonal islogical(M) % logical matrix ndims(M)==2 % 2D matrix all(size(M)==n) % square matrix
Unscored bonus:
Visualize the result as a graph where M represents the adjacency matrix:
% circular layout t = linspace(0, 2*pi, n+1)'; xy = [cos(t(1:end-1)) sin(t(1:end-1))]; subplot(121), spy(M) subplot(122), gplot(M, xy, '*-'), axis image
Solution Stats
Problem Comments
Solution Comments
Show commentsProblem Recent Solvers352
Suggested Problems
-
Get the area codes from a list of phone numbers
1076 Solvers
-
How to find the position of an element in a vector without using the find function
2822 Solvers
-
666 Solvers
-
Replace Nonzero Numbers with 1
457 Solvers
-
Write a function man that takes a row vector v and returns a matrix H as follows..
652 Solvers
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Any clue? Does this problem require great mathematics abilities ?
Not really, imagine in the simplest case that we could use the diagonals (ignoring this constraint), what the solution would look like? A chessboard pattern would solve it, wouldn't it? Now, how can we work around the constraint?
Hint? I don't have the slightest clue where to start. Rafael, your tip leaves me no less baffled.