class keep_index:
    """custom integer that can be called for its index value,
    easiest way to attach a static value to a dynamic value"""
    def __init__(self, value, index):
        self.value = str(value)
        self.index = index
        
    def __call__(self):
        return self.index
    
    def __repr__(self):
        return self.value

    def __lt__(self, other):
        return self.value < other

    def __le__(self, other):
        return self.value <= other

    def __eq__(self, other):
        return self.value == other

    def __ne__(self, other):
        return self.value != other

    def __gt__(self, other):
        return self.value > other

    def __ge__(self, other):
        return self.value >= other        

def index_table(table):
    """add the index of each item in the table"""
    ntable = []
    for row in table:
        ntable += [[[]]]
        for i, item in enumerate(row[0]):
            ntable[-1][-1].append(keep_index(item, i))
        ntable[-1].append(row[1])
    return ntable

def comb_list(seq, k):
    """    Algorithm by Gilward Kukel
    http://www.programmingforums.org/forum/showthread.php?t=4343

    returns a list of all k-combinations
    of the elements of sequence seq"""
    
    n=len(seq)
    if not 0<=k<=n:
        raise Exception,"0<=k<=len(seq) is not true"
    v=[]   #list of combinations
    #x: number of taken elements
    #y: number of rejected elements
    #we want to take k elements and reject n-k elements
    def f(x,y,a):
        if x==k:
            #we have taken enough elements, reject all remaining elements
            v.append(a)
            return
        if y==n-k:
            #we have rejected enough elements, take all remaining elements
            a.extend(seq[x+y:])
            v.append(a)
            return
        if (x<k):
            #take element seq[x+y]
            h=a+[seq[x+y]]
            f(x+1,y,h)
        if (y<n-k):
            #don't take element seq[x+y]
            f(x,y+1,a)            
    f(0,0,[])
    return v

def fetch(table, b):
    """fetch a column from the table"""
    '''
    [
    [[(0, 0), (0, 1)], [(0, 0), (2, 2)], [(0, 1), (2, 2)]],
    [[(0, 0), (1, 1)], [(0, 0), (2, 2)], [(1, 1), (2, 2)]],
    [[(1, 0), (0, 1)], [(1, 0), (2, 2)], [(0, 1), (2, 2)]],
    [[(1, 0), (1, 1)], [(1, 0), (2, 2)], [(1, 1), (2, 2)]]
    ]
    '''
    t = []
    for row in table:
        t.append([])
        for item in row[b]:
            t[-1].append(item)
    
    return t

def validate(col, out):
    """find out if a logical expression is possible for this
    column(s) (if there are two results for the same input)"""
    '''
    [[0, 0], [0, 1], [1, 0], [1, 1]], [0, 1, 1, 1]
    '''
    for find, flp in enumerate(col):
        for sind, slp in enumerate(col):
            if flp == slp and find != sind:
                if out[find] != out[sind]:
                    return False
    return True

def main(table):
    INPUTS  = len(table[0][0])
    OUTPUTS = len(table[0][1])
    ntable = index_table(table)

    # figure out each output column one by one
    for _output in range(OUTPUTS):

        # grab the output column from the table
        out = [row[1][_output] for row in ntable]

        # we can't go past "INPUT" number of columns in the expression
        for _input in range(1, INPUTS+1):
            
            choices = []
            
            for row in ntable:
                # get all combination of elements inside a
                # row that is _input'th elements long
                choices += [comb_list(row[0], _input)]

            for choice in range(len(choices[0])):
                # fetch the column of each combination
                columns = fetch(choices, choice)

                # validate it with the "vertical line test"
                if validate(columns, out):
                    print columns

if __name__ == '__main__':
    table = [[[0, 0], [0]],
             [[0, 1], [1]],
             [[1, 0], [1]],
             [[1, 1], [1]]]
    main(table)