# getting a submatrix of all true

Scott David Daniels scott.daniels at acm.org
Sun Jul 6 08:10:58 CEST 2003

```Folllowing Bengt and anton at vredegoor.doge.nl (Anton Vredegoor)'s leads,
the following code can be fast (at times).  It is quite sensitive to the
probability of non-zeroness, (.01 works well, the .o5 is nowhere near so
nice).

I get 2.25 min to do 25 x 25 at .05
2.75 min to do 30 x 30 at .05
It gets slow _very_ fast, but gets good numbers if the probability is low
.25 min to do 45 x 45 at .01
1.5 min to do 50 x 50 at .01

-Scott David Daniels
Scott.Daniels at Acm.Org (not fully back up yet, though).

Here's the code:
################################
# myopt.py
__version__ = '0.3'

try:
assert list(enumerate('ab')) == [(0, 'a'), (1, 'b')]
except NameError:
def enumerate(iterable):
# Not exact, but close enough
lst = list(iterable)
return zip(range(len(lst)), lst)

def bitcount(row):
'''Return the number of on bits in the integer argsA'''
assert row >= 0
result = 0
while row:
result += 1
lsbit = row & -row
row ^= lsbit
return result

def rowencode(vector):
'''convert from a buncha numbers to a bit-representation'''
bit = 1L
result = 0
for element in vector:
if element:
result |= bit
bit <<= 1
return result

'''convert from a bit-rep to a buncha numbers (at least as long as mask)'''
assert value >= 0
result = []
result.append(value & 1)
value >>= 1
return result

'''An answer represents a result calculation.'''
totalrequests = 0
totalcalcs = 0

'''The columns in colmask are the ones we keep.'''
self.rows = rows
self._score = None

def score(self):
'''Calculate the score lazily'''
self.__class__.totalrequests += 1
if self._score is None:
self.__class__.totalcalcs += 1
return self._score

def __repr__(self):
return '%s(%d:%s, %x):%s' % (self.__class__.__name__,
len(self.rows), self.rows,

totalcalls = 0

def choose(rows, keepcols, N=0, keeprows=None):
'''Choose rows and columns to keep.  Return an Answer for the choice'''
global totalcalls
totalcalls += 1
if keeprows is None:
keeprows = []
try:
while 0 == rows[N] & keepcols:
keeprows.append(N)
N += 1
except IndexError:

# a difference: some kept columns in this row are non-0
# must drop either those columns or this row

# Calculate result if we keep this row (drop problem columns)
withrow = choose(rows, keepcols & ~rows[N], N+1, keeprows + [N])

# Calculate result if we drop this row
skiprow = choose(rows, keepcols, N+1, keeprows)

# Choose the better answer (keep the row if everything is equal).
or withrow.score() >= skiprow.score()):
return withrow
else:
return skiprow

# The data used from the example
X = [ [1, 0, 0, 0, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 1, 0],
[0, 0, 0, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 1, 0, 0] ]

result = []
for element in row:
result.append(symbols[(1 & mask) * 2 + (element != 0)])
return ''.join(result)

'''Print the represented row'''
toohuge = len(data)
rowqueue = rows + [toohuge]
rowqueue.reverse()
nextrow = rowqueue.pop()
for rownumber, row in enumerate(data):
if nextrow > rownumber:
# This row was zapped
print '#', printrep(row, '01OI', keepcols)
else:
assert rownumber == nextrow # This row was kept
nextrow = rowqueue.pop()
print '_', printrep(row, '01~@', keepcols)
assert nextrow == toohuge and not rowqueue

'''Calculate the best-cut for a particular matrix'''
columns = max([len(row) for row in data])
rowdata = [rowencode(row) for row in data]
return choose(rowdata, (1L << columns) - 1)

def main(data=X):
global totalcalls

totalcalls = 0
print 'Requested: %s, Calculated: %s,' % (

print 'Total choose calls required: %s' % totalcalls

def rangen(rows, columns, probability=0.05):
'''create a rows by columns data table with 1s at the given probability'''
import random
result = []
for row in range(rows):
result.append([int(random.random() < probability)
for column in range(columns)])
return result

if __name__ == '__main__':
import sys
if len(sys.argv) < 2:
main(X)
else:
args = sys.argv[1:]
if '.' in args[-1]:
assert len(args) > 1
probability = float(args.pop())
else:
probability = .2

rows = int(args[0])
if len(args) == 1:
cols = rows
else:
assert len(args) == 2
cols = int(args[1])
main(rangen(rows, cols, probability))

```