## Matrix Fill-In

### January 12, 2016

The obvious solution first collects each cell containing 1 in a first pass and fills-in the matrix in a second pass:

```(define (fill-in m)
(let ((nrows (matrix-rows m))
(ncols (matrix-cols m))
(xs (list)))
(for (r 0 nrows)
(for (c 0 ncols)
(when (= (matrix-ref m r c) 1)
(set! xs (cons (cons r c) xs)))))
(let loop ((xs xs))
(cond ((null? xs) m)
(else (for (r 0 nrows)
(matrix-set! m r (cdar xs) 1))
(for (c 0 ncols)
(matrix-set! m (caar xs) c 1))
(loop (cdr xs)))))))```

This operates in time O(kmn) on an m × n matrix with k intial 1-cells:

```> (fill-in '#(
#(0 0 0 0 0)
#(0 0 0 0 0)
#(0 0 0 1 0)
#(1 0 0 0 0)
#(0 0 0 0 0)))
#(#(1 0 0 1 0)
#(1 0 0 1 0)
#(1 1 1 1 1)
#(1 1 1 1 1)
#(1 0 0 1 0))```

We used the matrix operations of the Standard Prelude. You can run the program at http://ideone.com/zDuUDl.

Advertisements

Pages: 1 2

### 9 Responses to “Matrix Fill-In”

1. Jussi Piitulainen said

Julia (0.4.1), seemed to work; findn returns the indices for non-zero values; colon is a special index that somehow stands for the whole range in that position; the assigned 1 ends up in every cell in the row or column.

```function mfi(A)
for (r,k) in findn(A)
A[r,:] = 1
A[:,k] = 1
end
end
```

(Happy new year!)

2. matthew said

Since we have a boolean matrix, let’s represent it with a Python big integer (which for an NxM matrix we can think of as an N-digit number in radix 2**N – and it’s convenient to take row 0 to be the least significant digit etc). It’s interesting that the fillin function doesn’t use the number of rows except to calculate the magic multiplier (which is eg. 0b100001000010000100001 for M = N = 5).

```def fillin(n,M,N):
radix = 2**M
magic = ((2**(M*N))-1)/(radix-1)
cols = 0; row = 0; cdigit = radix-1
while n > 0:
d = n%radix
row |= d
if d: cols += cdigit
n /= radix; cdigit *= radix
return (row * magic) | cols

def printmatrix(n,M,N):
radix = 2**M
for i in range(N):
print ('{0:0{1}b}'.format(n%radix,M))
n /= radix

def test(m,M,N):
p = lambda m: printmatrix(m,M,N)
f = lambda m: fillin(m,M,N)
print(bin(m)+":"); p(m); print; p(f(m)); print

test(int('10000000100000000000',2),5,5)
test(int('10000000100000000000',2),6,4)
```
```0b10000000100000000000:

00000
00000
00010
10000
00000

10010
10010
11111
11111
10010

0b10000000100000000000:

000000
100000
000000
000010

100010
111111
100010
111111
```
3. Mike said

Python version

```def fill(m):
r =  * len(m)
c = [int(any(col)) for col in zip(*m)]
m[:] = [r if any(row) else c for row in m]
```
4. Mike said

Here’s a solution using Python / Numpy arrays

```def fill(m):
m |= (m.any(axis=0) | m.any(axis=1, keepdims=True))

#test:
m = np.array([
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,1,0],
[1,0,0,0,0],
[0,0,0,0,0]])
fill(m)
print(m)
```

Output:

```[[1 0 0 1 0]
[1 0 0 1 0]
[1 1 1 1 1]
[1 1 1 1 1]
[1 0 0 1 0]]
```
5. Vikas Dhyani said

Java Code to populate and manipulate the matrix:-

public class MatrixFillIn {
int[][] matrix = new int;

public void populateMatrix() {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (i == 0 & j == 0 || i == 2 & j == 4)
// if (i == 3 & j == 0)
matrix[i][j] = 1;
}

}
}

public void printMatrix() {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
System.out.print(matrix[i][j]);
}
System.out.println("");
}
}

public void rearrangeMatrix() {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (matrix[i][j] == 1) {
matrix[i][j] = 2;
// for given i, all js are marked as 1 and added entry
for (int k = 0; k < 5; k++) {
if (matrix[i][k] == 0)
matrix[i][k] = 2;
}
// for given j, all is are marked as 1 and added entry
for (int l = 0; l < 5; l++) {
if (matrix[l][j] == 0)
matrix[l][j] = 2;
}

}
}
}

for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (matrix[i][j] == 2) {
matrix[i][j] = 1;

}
}
}
}

public static void main(String args[]) {
MatrixFillIn m = new MatrixFillIn();
m.populateMatrix();
m.printMatrix();
m.rearrangeMatrix();
m.printMatrix();
}
}

======

I'll really appreciate is someone could improve the complexity of this algorithm. currently it is 2n^2

6. Yuriy V. said

Java Script. Works under any browser

// Initial matrix 5×5
var matrix1 = [ [0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,1,0],
[1,0,0,0,0],
[0,0,0,0,0]];
// Empty matrix 5×5. Result will be here
var matrix2 = [ [0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0]];
// correct matrix printing function
function print(matrixName) {
for(i=0;i<5;i++) {
for(j=0;j<5; j++){
document.write (matrixName[i][j] + " ");
};
document.write("”);
};
}; // end of function

// Print initial matrix
document.write(“”+”Initial matrix”+”” );
print (matrix1);

// main processing
for(var row=0; row < 5; row++) {
for(var column=0; column < 5; column++){
if (matrix1[row][column] == 1) {
//cycle for "1" adding to rows and columns
for(var i=0; i < 5; i++) {
matrix2[row][i] = 1;
matrix2[i][column] = 1;
};
};
}; // columns cycle
}; //rows cycle

// Print Final marix
document.write("”+”Final result”+”” );
print (matrix2);

===============================================================
You will see Result of program in browser window:

Initial matrix
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
1 0 0 0 0
0 0 0 0 0

Final result
1 0 0 1 0
1 0 0 1 0
1 1 1 1 1
1 1 1 1 1
1 0 0 1 0

7. Yuriy V. said

In previous code comand ” ” was shown as “”

8. Yuriy V. said

This comand could not be shown in comments: BR /

9. Yuriy V. said

// Initial matrix 5×5
var matrix1 = [ [0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,1,0],
[1,0,0,0,0],
[0,0,0,0,0]];
// Empty matrix 5×5. Result will be here
var matrix2 = [ [0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0]];
// correct matrix printing function
function print(matrixName) {
for(i=0;i<5;i++) {
for(j=0;j<5; j++){
document.write (matrixName[i][j] + " ");
};
document.write("<BR/>");
};
}; // end of function

// Print initial marix
document.write("<br/>"+"Initial matrix"+"<br/>" );
print (matrix1);
// main processing
for(var row=0; row < 5; row++) {
for(var column=0; column < 5; column++){
if (matrix1[row][column] == 1) {
//cycle for "1" adding to rows and columns
for(var i=0; i < 5; i++) {
matrix2[row][i] = 1;
matrix2[i][column] = 1;
};
};
}; // columns
}; //rows

// Print Final marix
document.write("<br/>"+"Final result"+"<br/>" );
print (matrix2);