http://stackoverflow.com/questions/5694866/fast-matching-tuples-based-on-condition

__main__.py

from constraint import AllDifferentConstraint, Problem
from ruleparser import RuleParser


def solutions(rule, possible_values):
    problem = Problem()

    # each tuple should occur only once in the solution
    problem.addConstraint(AllDifferentConstraint())

    # add constraints defined by the rule
    p = RuleParser()
    for variables, constraint in p.parse(rule):
        problem.addConstraint(constraint, variables)

    # declare all variables and define their possible values
    problem.addVariables(p.seen_variables, possible_values)

    # yield solutions
    short_names = dict((val, "T%d" % i)
                       for i, val in enumerate(possible_values, 1))
    for solution in problem.getSolutionIter():
        yield [(variable, short_names[value])
               for variable, value in sorted(solution.items())]


if __name__ == "__main__":
    for solution in solutions("T(1)[1] = T(2)[1] AND T(1)[3]>=T(3)[1]",
                              [(1, 2, 3, 4), (3, 2, 4), (4,), (1, 5, 3, 6, 7)]):
        print(", ".join("%s: %s" % t for t in solution))

ruleparser.py

from collections import namedtuple
from operator import eq, ne, gt, lt, le, ge

try: reduce = reduce
except NameError:
    from functools import reduce # py3k

from lepl  import Digit, Drop, DroppedSpace, Eos, Literal, Or, args

__all__ = ['RuleParser']

OPERATORS = {'=': eq, '!=': ne, '>': gt, '<': lt, '<=': le, '>=': ge}

Item = namedtuple('Item', 'var i')

class RuleParser(object):
    """
    >>> import pprint
    >>> pp = pprint.pprint
    >>> p = RuleParser()
    >>> pp(list(p.parse(
    ...    'T(1)[2] = T(1)[1] AND T(2)[3] != T(3)[4] AND'
    ...    'T(4) [5] < T(5)[6] AND T(7)[8] <= T(9)[10]'
    ...    ))) # doctest:+ELLIPSIS
    [(('T(1)', 'T(1)'), <function contraint<2,  =, 1> at 0x...>),
     (('T(2)', 'T(3)'), <function contraint<3, !=, 4> at 0x...>),
     (('T(4)', 'T(5)'), <function contraint<5,  <, 6> at 0x...>),
     (('T(7)', 'T(9)'), <function contraint<8, <=, 10> at 0x...>)]
    >>> sorted(p.seen_variables)
    ['T(1)', 'T(2)', 'T(3)', 'T(4)', 'T(5)', 'T(7)', 'T(9)']
    >>> f = p._parse
    >>> f('T(0)[1] <= T(11)[2]')
    [(Item(var='T(0)', i=1), '<=', Item(var='T(11)', i=2))]
    >>> 'T(1)' in p.seen_variables
    True
    >>> 'T(11)' not in p.seen_variables
    True
    >>> pp(f('T(1)[2] = T(1)[1] AND T(2)[3] != T(3)[4]'))
    [(Item(var='T(1)', i=2), '=', Item(var='T(1)', i=1)),
     (Item(var='T(2)', i=3), '!=', Item(var='T(3)', i=4))]
    """

    def __init__(self):
        self._seen_variables = set()
        
        # define parser
        # allowed operators
        op = reduce(Or, map(Literal, OPERATORS.keys())) 
        # index value
        index = Digit()[1:, ...] # \d+

        with DroppedSpace(): # ignore whitespace
            # T(i)
            T = 'T' & ('(' & index) & ')' > (lambda x: ''.join(map(str, x)))
            # T(i)[j]
            item = (T & Drop('[') & (index >> int) & Drop(']')) > args(Item)
            # T(j)[i] op T(k)[l]
            clause =  item & op & item > tuple
            # Clause (AND Clause)*
            condition = clause[1:, Drop('AND')]
            # match only complete strings
            rule = condition & Eos()
        self._parse = rule.get_parse()
        
    def parse(self, rule_str):
        for first, op, second in self._parse(rule_str):
            variables = first.var, second.var
            self._seen_variables.update(variables)
            constraint = _make_constraint(first.i, op, second.i)
            yield variables, constraint

    @property
    def seen_variables(self):
        return tuple(self._seen_variables)

def _make_constraint(i, op, j):
    i -= 1; j -= 1
    def constraint(a, b):
        # a[i] op b[j]
        return len(a) > i and len(b) > j and OPERATORS[op](a[i], b[j])
    constraint.__name__ = 'contraint<%s, %2s, %s>' % (i+1, op, j+1)
    return constraint