I am solving a problem such that if an element in an MxN matrix is 0, its entire row and column are set to 0.
First, two variables zero_row and zero_col are introduced to store the row and column which need to be set to 0, respectively. Next, I loop though the elements in the matrix, set the bit offset of row in zero_row and the bit offset of column in zero_col to 1 if the element equals to 0. Then, I loop through the matrix again and set each row and column to zero if the bit offsets are set to 1 in zero_row and zero_col.
zero_row and zero_col are set to 0 initially. So I presume it is an integer type. I am working on a 64bits computer. Therefore I thought the maximum bit I could set is 64 bits (per integer). I am curious why the code still work correctly with an array of 3x144. The column size 144 bits is obviously larger than 64 bits... Does Python automatically do "typecasting" ?? or perhaps anyone can point me to the documentations which explain the fundamental. Thanks.
import numpy
class Matrix:
def __init__(self):
pass
def check_matrix(self, input_mat):
zero_row = 0
zero_col = 0
for row in xrange(len(input_mat)):
for col in xrange(len(input_mat[row])):
if zero_row >> row & 1 == 0 or zero_col >> col & 1 == 0:
if input_mat[row][col] == 0:
zero_row = zero_row | 1 << row
zero_col = zero_col | 1 << col
return [zero_row, zero_col]
def set_matrix(self, input_mat, zero_row, zero_col):
for row in xrange(len(input_mat)):
for col in xrange(len(input_mat[row])):
if (zero_row >> row) & 1 == 1 or (zero_col >> col) & 1 == 1:
input_mat[row][col] = 0
return input_mat
m = Matrix()
# input_arr = numpy.array([[1,1,1], [2, 0, 2], [3, 3, 3]])
# input_arr = numpy.array([[1,1,1], [2, 2, 2], [0, 3, 0]])
input_arr = numpy.array([
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,11,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,11,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,11,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,3,0]
])
[zero_row, zero_col] = m.check_matrix(input_arr)
print bin(zero_row), " ", bin(zero_col)
print m.set_matrix(input_arr, zero_row, zero_col)
Results:
0b100 0b101000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
[[ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0]
[ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 2 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
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 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 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 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]]
