getting a submatrix of all true

[Anton Vredegoor]

John Hunter <jdhunter at ace.bsd.uchicago.edu> wrote:

>>>>>> "Bengt" == Bengt Richter <bokr at oz.net> writes:
>    Bengt> Brute force seems to work on this little example. Maybe it
>    Bengt> can be memoized and optimized and/or whatever to handle
>    Bengt> your larger matrix fast enough?
>
>Thanks for the example.  Unfortunately, it is too slow even for
>moderate size matrices (30,10).  I've been running it for over two
>hours for a 30x10 matrix and it hasn't finished.  And my data are
>1000x100!

I posted a somewhat long version before (inspired by Bengts idea) but
I remembered an easier way to generate all combinations, and also I
noticed that there is freedom in choosing to analyze rows or columns,
which can be computationally advantageous. Below is a version that
depends mostly on 2**N where N is the smallest of those two values.
Unfortunately 2**100 is still way to big a number, but my code can now
routinely solve 100x15 matrices ...

>Last night, I began to formulate the problem as a logic statement,
>hoping this would give me an idea of how to proceed.  But no progress
>yet.  But I have come to the conclusion that with P ones, brute force
>requires 2^P combinations.  With 1000x100 with 5% missing that gives
>me 2^5000.  Not good.  

IMO it depends (except for the amount time spent in copying data of
course) on the smallest of the number of rows or columns, so that's
2**100 in this case. Maybe for some matrices, your number is
preferable?

>Thanks for your suggestion, though.  If you have any more thoughts,
>let me know.

I hope you don't mind me following this too :-) Nice problem, and I'm
not so sure about my math as I sound above, if anyone can prove me
right or wrong I'd be happy anyway ...

Anton

---

class ScoreMatrix:
    
    def __init__(self, X):
        n1,n2 = len(X),len(X[0])
        if n2<n1:
            self.X = zip(*X)
            self.rotated = True
            n = n2
        else:
            self.X = X
            n = n1
            self.rotated = False
        self.R = range(n)
        self.count = 2**n
    
    def __getitem__(self,i):
        #score selected rows and columns by index
        if not (-1<i<self.count): raise IndexError
        rows =[x for j,x in enumerate(self.R) if 1<<j &i] 
        if rows:
            Y = [self.X[i] for i in rows]
            Z = [(i,z) for i,z in enumerate(zip(*Y)) if 1 not in z]
            cols = [i for i,z in Z]
            score = sum(map(len,[z for i,z in Z]))
            if self.rotated:  return score,cols,rows
            else: return score,rows,cols
        else: return 0,[],[]

def test():
    from random import random,randint
    f = .05
    r,c = 100,15
    X=[]
    for i in range(r):
        X.append([])
        for j in range(c):
            X[i].append(int(random()<f))
    M = ScoreMatrix(X)
    highscore = 0,[],[]
    for i,sc in enumerate(M):
        if sc > highscore:
            mi,highscore = i,sc
    sc,rows,cols = highscore
    print "maximum score:       %s" %(sc)
    print "index of this score: %s" %(mi)
    print "tabledata:"
    for i,r in enumerate(X):
        for j,c in enumerate(r):
            if i in rows and j in cols: print c,
            else: print 'x',
        print

if __name__=='__main__':
    test()