On Feb 1, 8:17 pm, Karthik Gurusamy <[EMAIL PROTECTED]> wrote: [...] > def strip_sort (a, b): > if a[0] < b[0]: > return -1 > if a[0] > b[0]: > return 1 > if a[0] == 'L': return -1 > return 0 > > def overlaps (strips_given): > s2 = [((s[0], 'L', i) , (s[1], 'R', i)) for i,s in > enumerate(strips_given)] > strips = [] > for s in s2: > strips.append(s[0]) > strips.append(s[1]) > clique = set() > edges = [] > strips.sort(cmp=strip_sort) > for s in strips: > node = s[2] > if s[1] == 'L': > clique.add(node) > if s[1] == 'R': > new_edges = [(node, i) for i in clique if i != node] > edges += new_edges > clique.remove(node) > return edges
Interesting. This is a long version of the algorithm I posted earlier. -- Arnaud -- http://mail.python.org/mailman/listinfo/python-list
