## 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

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.

(Happy new year!)

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).

Python version

Here’s a solution using Python / Numpy arrays

Output:

Java Code to populate and manipulate the matrix:-

public class MatrixFillIn {

int[][] matrix = new int[5][5];

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

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

In previous code comand ” ” was shown as “”

This comand could not be shown in comments: BR /

// 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);