Skip to content

Instantly share code, notes, and snippets.

@nailor
Created November 29, 2011 09:07
Show Gist options
  • Save nailor/1404104 to your computer and use it in GitHub Desktop.
Save nailor/1404104 to your computer and use it in GitHub Desktop.
def form_preference_list(image, edge, others):
def g():
for other_edge in others:
yield (other_edge, image.row_dist(edge, other_edge))
return [x[0] for x in sorted(g(), key=operator.itemgetter(1))]
def stable_matching(image, lefts, rights):
free_left = set(lefts)
right_edges = set(rights)
result = []
def _match(edge):
for pair in result:
if edge in pair:
return pair
while free_left:
left = free_left.pop()
print 'Lefts %d' % len(free_left)
for preferred in form_preference_list(image, left, right_edges):
if not _match(preferred):
result.append((preferred, left))
break
else:
right_pref = form_preference_list(image, preferred, lefts)
pair = _match(preferred)
if right_pref.index(pair[1]) > right_pref.index(left):
free_left.add(pair[1])
result.remove(pair)
result.append((preferred, left))
break
return result
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment