minimal_subsets

_minimal_subsets.py

#pythran export ok_to_add((complex, complex[:]), (complex, complex[:]), float)
def ok_to_add (item, c, dmin):
    '''item,c are (center, [list of pts])
    '''
    center0, W0s = item
    center1, W1s = c
    return all (abs (center0 - x) >= dmin for x in W1s) and \
        all (abs (center1 - x) >= dmin for x in W0s)

#pythran export find_other_set ((complex, complex[:]) list list, (complex, complex[:]), int, float)
def find_other_set (possible_sets, other_item, limit, dmin):
    # Is there a set I can move other_item into?
    for other_set in possible_sets:
        if len(other_set) < limit and all (ok_to_add (c, other_item, dmin) for c in other_set):
            return other_set, other_item
    return None, None

minimal_subsets.py

def try_swap(item, sets, limit, dmin):
    # Is there a set I can move points out of to make room for item?
    for s in sets:
        # Can I move other_items out of set s into other_sets to make room for item?
        # Here are all the items that have distance violations for adding item into set s
        other_items = [c for c in s if not ok_to_add (item, c, dmin)]
        possible_sets = [s2 for s2 in sets if s2 is not s]
        # Can we find new homes for other_items?
        stuffs = [find_other_set (possible_sets, other_item, limit, dmin) for other_item in other_items]
        stuffs2 = [find_other_set2 (possible_sets, other_item, limit, dmin) for other_item in other_items]
        other_sets, other_items = zip(*stuffs)
        if all(_ is not None for _ in other_sets):
            return s, other_sets, other_items

    return None, None, None

def types(a):
    try:
        return ([types(x) for x in a])
    except:
        return type(a)

@profile
def find_other_set (possible_sets, other_item, limit, dmin):
     # Is there a set I can move other_item into?
    for other_set in possible_sets:
        if len(other_set) < limit and all (ok_to_add (c, other_item, dmin) for c in other_set):
            return other_set, other_item
    return None, None

from _minimal_subsets import find_other_set as find_other_set2