# -*- coding: utf-8 -*-

# import numpy as np
import itertools
import math
import time
import random
start_time = time.time()

# -*- coding: utf-8 -*-

import numpy as np
import random

# Enter the number of Men and Women (M>=W)
# M = 4
# W = 4

# Enter the arbitrary preference profile

# Example 1 (M,W)=(4,4)

M=4
W=4
RM = {1:(1, 2, 3, 4, 0),
      2:(2, 1, 4, 3, 0),
      3:(3, 4, 1, 2, 0),
      4:(4, 3, 2, 1, 0)}
RW= {1:(4, 3, 2, 1, 0),
     2:(3, 4, 1, 2, 0),
     3:(2, 1, 4, 3, 0),
     4:(1, 2, 3, 4, 0)}

'''
# Example 2 (M,W)=(2,2)
M=2
W=2
RM = {1:(1, 2, 0),
      2:(2, 1, 0)}
RW= {1:(2, 1, 0),
     2:(1, 2, 0)}
'''

'''
# Random preference profile (IR complete)
RM = dict()
RW = dict()
for m in range(1, M+1):
    RM[m] = np.array(random.sample(range(1, W + 1), k=W) + [0])
for w in range(1, W+1):
    RW[w] = np.array(random.sample(range(1, M + 1), k=M) + [0])
'''

# 男女の人数
print("#M =", M)
print("#W =", W)

#Preference Profile の表示
print("------------------------------")
print("Preference Profile")
for m in range(1, M + 1):
    print('R_m{} = '.format(m),RM[m])
print(" ")
for w in range(1, W + 1):
    print('R_w{} = '.format(w), RW[w])
print("------------------------------")


# 選好順位の数字を返す関数R_fを作成
def MakeRf(R, Mens):
    if Mens == True:
        NM = M
        NW = W
    else:
        NM = W
        NW = M
    Rf = dict()
    for m in range(1, NM + 1):
        Rf[m]=np.zeros(NW+1)
        for i in range(0, NW + 1):
            w = R[m][i]
            Rf[m][w] = i + 1
    '''
    if Mens == True:
        for m in range(1, NM + 1):
                print('Rf_m{} = '.format(m),Rf[m])
    else:
        for m in range(1, NM + 1):
                print('Rf_w{} = '.format(m),Rf[m])
    '''
    return Rf

def nCr(n, r):
    f = math.factorial
    return f(n) // f(r) // f(n - r)


def nPr(n, r):
    f = math.factorial
    return f(n) // f(n - r)


Rmf = MakeRf(RM, True)
Rwf = MakeRf(RW, False)


# 全てのマッチングを列挙
N = M + W
print(" ")

Numberlist = [0] * M + [w+1 for w in range(W)]
print("All mens can match with...", Numberlist)

A = list(itertools.permutations(Numberlist, M))

CP = 0
for i in range(M - W, M + 1):
    CP += nCr(M, i) * nPr(W, M - i)
# print("CP=", CP)

matching_all = sorted(set(A))

'''
print("len(A)=", len(A))
print("(m+w)Pm=", nPr(M + W, M))
'''
print("All matching list=")
print(matching_all)
print('#all matchings=',len(matching_all))


def isStable(matching):
    StableCheck = 1 # SC=1のときStable,0のときUnstable
    print(" ")
    print("matching μ =", matching)
    # IR?
    for m in range(M):
        mm = m + 1
        if matching[mm - 1] != 0: #異性とマッチしているときだけ調べれば良い
            ww = int(matching[mm - 1]) # matching[i]で(mm,ww)がマッチ
            if (Rmf[mm][ww] < Rmf[mm][0]) and (Rwf[ww][mm] < Rwf[ww][0]):
                print("(m{},w{}): IR".format(mm,ww))
                StableCheck = 1 * StableCheck
            else:
                print("(m{},w{}): not IR".format(mm,ww))
                StableCheck = 0 * StableCheck
    # Is there a blocking pair(bm,bw)?
    if StableCheck == 1:
        print("IR condition is satisfied.")
        for p in range(M):
            for q in range(W):
                bm = p + 1
                bw = q + 1
                match2bm = int(matching[bm - 1])
                if bw in matching: #bwがマッチしている相手を調べる
                    match2bw = matching.index(bw) + 1
                else:
                    match2bw = 0
                if (Rmf[bm][match2bm] > Rmf[bm][bw]) and (Rwf[bw][match2bw] > Rwf[bw][bm]):
                    print("A pair (m{},w{}) blocks the matching. (μ(m{})={}, μ(w{})={})".format(bm,bw,bm,match2bm,bw,match2bw))
                    StableCheck = 0
    if StableCheck == 1:
        print("No pair blocks the matching.")
        print("Matching {} is stable.".format(matching))
        return True
    else:
        StableCheck = 1
        print("Matching {} is not stable.".format(matching))
        return False

StableMatch = set()
for i in range(CP):  # Is matching[i] Stable?
    if isStable(matching_all[i]):
        StableMatch.add(matching_all[i])

StableMatch = sorted(StableMatch)
print(" ")
print("Stable Matching=")
print(StableMatch)



#------------------------------------------------------------------------------#
#Lattice
T = len(StableMatch)

for i in range(T):
    print(" ")
    #print("μ{} = {}".format(i, StableMatch[i]))
    for j in range(T):  # SM[i]とSM[j]を比べる
        if not i == j:
            LgtR = 0
            LltR = 0
            LeqR = 0
            for k in range(M):
                Lw = int(StableMatch[i][k])
                Rw = int(StableMatch[j][k])
                if Rmf[k + 1][Lw] < Rmf[k + 1][Rw]:  # Lw>(k)Rw
                    LgtR = 1
                elif Rmf[k + 1][Lw] > Rmf[k + 1][Rw]:  # Lw<(k)Rw
                    LltR = 1
                else:  # Lw~(k)Rw
                    LeqR = 1
            if (LgtR == 1) and (LltR == 1): #μi~μj
                join = [0] * M # μi ∨ μj
                meet = [0] * M # μi ∧ μj
                for k in range(M):
                    Lw = int(StableMatch[i][k])
                    Rw = int(StableMatch[j][k])
                    if Rmf[k + 1][Lw] < Rmf[k + 1][Rw]:  # Lw>(k)Rw
                        join[k] = Lw
                        meet[k] = Rw
                    elif Rmf[k + 1][Lw] >= Rmf[k + 1][Rw]:  # Lw<(k)Rw
                        join[k] = Rw
                        meet[k] = Lw
                ij_join = StableMatch.index(tuple(join))
                ij_meet = StableMatch.index(tuple(meet))
                print("μ{} ~ {} = μ{}, μ{} ∨ μ{} = {} = μ{}, μ{} ∧ μ{} = {} = μ{}.".format(i,StableMatch[j],j, i,j,join,ij_join, i,j,meet,ij_meet))
            elif (LgtR == 1) and (LltR == 0):
                print("μ{} ≧ {} = μ{}".format(i,StableMatch[j],j))
            elif (LgtR == 0) and (LltR == 1):
                print("μ{} ≦ {} = μ{}".format(i,StableMatch[j],j))
            else:
                print("Error!")
        else:
            print("μ{} = {} = μ{}".format(i,StableMatch[j],j))

duration = time.time() - start_time
print(" ")
print('Running time=',format(duration),'s')