'''matchings.py

   Jeff Ondich, 13 January 2009

   Some tools for doing brute-force enumeration of stable matches.
   Not well documented--just hacked together quickly to allow me
   to play around with some examples.
'''

import sys

women = ['Alice', 'Bella', 'Carmen', 'Dora']
men = ['Ernie', 'Fred', 'George', 'Harry']

# prefs[j][k] gives the rank assigned by person j to person
# k of the opposite sex.  Thus, if malePrefs[0][2] = 2,
# then Ernie ranks Carmen 3rd (of ranks 0, 1, 2, and 3, 2
# is the third).
malePrefs = [[0, 1, 2, 3],
             [2, 1, 3, 0],
             [2, 3, 0, 1],
             [2, 3, 1, 0]]

femalePrefs = [[1, 2, 3, 0],
               [2, 3, 1, 0],
               [2, 0, 3, 1],
               [1, 3, 0, 2]]

def getPermutations(n):
    permutationList = []

    def permute(permutation, left):
        n = len(permutation)
        if left >= n:
            return
        
        if left + 1 == n:
            permutationList.append(permutation[:]) # clone
            return

        for k in range(left, n):
            permutation[left], permutation[k] = permutation[k], permutation[left]
            permute(permutation, left + 1)
            permutation[left], permutation[k] = permutation[k], permutation[left]

    permutation = range(n)
    permute(permutation, 0)
    return permutationList

def printPreferences(out, proposers, responders, proposerPrefs):
    for k in range(len(proposers)):
        out.write('%-10s' % (proposers[k] + ':'))
        pairs = zip(proposerPrefs[k], responders)
        pairs.sort()
        for pair in pairs:
            out.write('%-10s' % pair[1])
        out.write('\n')

def printMatching(out, matching, proposers, responders):
    for pair in matching:
        out.write('%s <=> %s\n' % (proposers[pair[0]], responders[pair[1]]))

def isStable(matching, proposerPrefs, responderPrefs):
    n = len(matching)
    proposerPartners = {}
    responderPartners = {}
    for pair in matching:
        proposerPartners[pair[0]] = pair[1]
        responderPartners[pair[1]] = pair[0]

    for j in range(n):
        for k in range(n):
            #print '(j, k) = (%d, %d) = (%s, %s)' % (j, k, men[j], women[k])
            #print 'current = (%s, %s), (%s, %s)' % (men[j], women[proposerPartners[j]], men[responderPartners[k]], women[k])
            #print '%s\'s preference for %s is = %d' % (men[j], women[k], proposerPrefs[j][k])
            #print '%s\'s preference for %s is = %d' % (men[j], women[proposerPartners[j]], proposerPrefs[j][proposerPartners[j]])
            #print '%s\'s preference for %s is = %d' % (women[k], men[j], responderPrefs[k][j])
            #print '%s\'s preference for %s is = %d' % (women[k], men[responderPartners[k]], responderPrefs[k][responderPartners[k]])
            if proposerPrefs[j][k] < proposerPrefs[j][proposerPartners[j]]\
                  and responderPrefs[k][j] < responderPrefs[k][responderPartners[k]]:
                return False

    return True

def getHappiness(matching, proposerPrefs, responderPrefs):
    n = len(matching)
    proposerHappiness = 0
    responderHappiness = 0
    for pair in matching:
        proposerHappiness += proposerPrefs[pair[0]][pair[1]]
        responderHappiness += responderPrefs[pair[1]][pair[0]]
    return (proposerHappiness, responderHappiness)
    
def printAllStableMatchings(out, proposers, responders, proposerPrefs, responderPrefs):
    n = len(proposers)
    for p in getPermutations(n):
        matching = zip(range(n), p)
        if isStable(matching, proposerPrefs, responderPrefs):
            printMatching(out, matching, proposers, responders)
            (thisTotal, thatTotal) = getHappiness(matching, proposerPrefs, responderPrefs)
            out.write('Happiness: %d + %d = %d\n' % (thisTotal, thatTotal, thisTotal + thatTotal))
            out.write('\n')

printPreferences(sys.stdout, men, women, malePrefs)
sys.stdout.write('\n')
printPreferences(sys.stdout, women, men, femalePrefs)
sys.stdout.write('\n')

#matching = [[0,0], [1,1], [2,3], [3,2]]
#printMatching(sys.stdout, matching, men, women)
#print isStable(matching, malePrefs, femalePrefs)
#printAllStableMatchings(sys.stdout, men, women, malePrefs, femalePrefs)
printAllStableMatchings(sys.stdout, women, men, femalePrefs, malePrefs)