SHARE
TWEET

Untitled

a guest May 25th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # -*- coding: utf-8 -*-
  2.  
  3. # import numpy as np
  4. import itertools
  5. import math
  6. import time
  7. import random
  8. start_time = time.time()
  9.  
  10. # -*- coding: utf-8 -*-
  11.  
  12. import numpy as np
  13. import random
  14.  
  15. # Enter the number of Men and Women (M>=W)
  16. # M = 4
  17. # W = 4
  18.  
  19. # Enter the arbitrary preference profile
  20.  
  21. # Example 1 (M,W)=(4,4)
  22.  
  23. M=4
  24. W=4
  25. RM = {1:(1, 2, 3, 4, 0),
  26.       2:(2, 1, 4, 3, 0),
  27.       3:(3, 4, 1, 2, 0),
  28.       4:(4, 3, 2, 1, 0)}
  29. RW= {1:(4, 3, 2, 1, 0),
  30.      2:(3, 4, 1, 2, 0),
  31.      3:(2, 1, 4, 3, 0),
  32.      4:(1, 2, 3, 4, 0)}
  33.  
  34. '''
  35. # Example 2 (M,W)=(2,2)
  36. M=2
  37. W=2
  38. RM = {1:(1, 2, 0),
  39.       2:(2, 1, 0)}
  40. RW= {1:(2, 1, 0),
  41.      2:(1, 2, 0)}
  42. '''
  43.  
  44. '''
  45. # Random preference profile (IR complete)
  46. RM = dict()
  47. RW = dict()
  48. for m in range(1, M+1):
  49.     RM[m] = np.array(random.sample(range(1, W + 1), k=W) + [0])
  50. for w in range(1, W+1):
  51.     RW[w] = np.array(random.sample(range(1, M + 1), k=M) + [0])
  52. '''
  53.  
  54. # 男女の人数
  55. print("#M =", M)
  56. print("#W =", W)
  57.  
  58. #Preference Profile の表示
  59. print("------------------------------")
  60. print("Preference Profile")
  61. for m in range(1, M + 1):
  62.     print('R_m{} = '.format(m),RM[m])
  63. print(" ")
  64. for w in range(1, W + 1):
  65.     print('R_w{} = '.format(w), RW[w])
  66. print("------------------------------")
  67.  
  68.  
  69. # 選好順位の数字を返す関数R_fを作成
  70. def MakeRf(R, Mens):
  71.     if Mens == True:
  72.         NM = M
  73.         NW = W
  74.     else:
  75.         NM = W
  76.         NW = M
  77.     Rf = dict()
  78.     for m in range(1, NM + 1):
  79.         Rf[m]=np.zeros(NW+1)
  80.         for i in range(0, NW + 1):
  81.             w = R[m][i]
  82.             Rf[m][w] = i + 1
  83.     '''
  84.     if Mens == True:
  85.         for m in range(1, NM + 1):
  86.                 print('Rf_m{} = '.format(m),Rf[m])
  87.     else:
  88.         for m in range(1, NM + 1):
  89.                 print('Rf_w{} = '.format(m),Rf[m])
  90.     '''
  91.     return Rf
  92.  
  93. def nCr(n, r):
  94.     f = math.factorial
  95.     return f(n) // f(r) // f(n - r)
  96.  
  97.  
  98. def nPr(n, r):
  99.     f = math.factorial
  100.     return f(n) // f(n - r)
  101.  
  102.  
  103. Rmf = MakeRf(RM, True)
  104. Rwf = MakeRf(RW, False)
  105.  
  106.  
  107. # 全てのマッチングを列挙
  108. N = M + W
  109. print(" ")
  110.  
  111. Numberlist = [0] * M + [w+1 for w in range(W)]
  112. print("All mens can match with...", Numberlist)
  113.  
  114. A = list(itertools.permutations(Numberlist, M))
  115.  
  116. CP = 0
  117. for i in range(M - W, M + 1):
  118.     CP += nCr(M, i) * nPr(W, M - i)
  119. # print("CP=", CP)
  120.  
  121. matching_all = sorted(set(A))
  122.  
  123. '''
  124. print("len(A)=", len(A))
  125. print("(m+w)Pm=", nPr(M + W, M))
  126. '''
  127. print("All matching list=")
  128. print(matching_all)
  129. print('#all matchings=',len(matching_all))
  130.  
  131.  
  132. def isStable(matching):
  133.     StableCheck = 1 # SC=1のときStable,0のときUnstable
  134.     print(" ")
  135.     print("matching μ =", matching)
  136.     # IR?
  137.     for m in range(M):
  138.         mm = m + 1
  139.         if matching[mm - 1] != 0: #異性とマッチしているときだけ調べれば良い
  140.             ww = int(matching[mm - 1]) # matching[i]で(mm,ww)がマッチ
  141.             if (Rmf[mm][ww] < Rmf[mm][0]) and (Rwf[ww][mm] < Rwf[ww][0]):
  142.                 print("(m{},w{}): IR".format(mm,ww))
  143.                 StableCheck = 1 * StableCheck
  144.             else:
  145.                 print("(m{},w{}): not IR".format(mm,ww))
  146.                 StableCheck = 0 * StableCheck
  147.     # Is there a blocking pair(bm,bw)?
  148.     if StableCheck == 1:
  149.         print("IR condition is satisfied.")
  150.         for p in range(M):
  151.             for q in range(W):
  152.                 bm = p + 1
  153.                 bw = q + 1
  154.                 match2bm = int(matching[bm - 1])
  155.                 if bw in matching: #bwがマッチしている相手を調べる
  156.                     match2bw = matching.index(bw) + 1
  157.                 else:
  158.                     match2bw = 0
  159.                 if (Rmf[bm][match2bm] > Rmf[bm][bw]) and (Rwf[bw][match2bw] > Rwf[bw][bm]):
  160.                     print("A pair (m{},w{}) blocks the matching. (μ(m{})={}, μ(w{})={})".format(bm,bw,bm,match2bm,bw,match2bw))
  161.                     StableCheck = 0
  162.     if StableCheck == 1:
  163.         print("No pair blocks the matching.")
  164.         print("Matching {} is stable.".format(matching))
  165.         return True
  166.     else:
  167.         StableCheck = 1
  168.         print("Matching {} is not stable.".format(matching))
  169.         return False
  170.  
  171. StableMatch = set()
  172. for i in range(CP):  # Is matching[i] Stable?
  173.     if isStable(matching_all[i]):
  174.         StableMatch.add(matching_all[i])
  175.  
  176. StableMatch = sorted(StableMatch)
  177. print(" ")
  178. print("Stable Matching=")
  179. print(StableMatch)
  180.  
  181.  
  182.  
  183. #------------------------------------------------------------------------------#
  184. #Lattice
  185. T = len(StableMatch)
  186.  
  187. for i in range(T):
  188.     print(" ")
  189.     #print("μ{} = {}".format(i, StableMatch[i]))
  190.     for j in range(T):  # SM[i]とSM[j]を比べる
  191.         if not i == j:
  192.             LgtR = 0
  193.             LltR = 0
  194.             LeqR = 0
  195.             for k in range(M):
  196.                 Lw = int(StableMatch[i][k])
  197.                 Rw = int(StableMatch[j][k])
  198.                 if Rmf[k + 1][Lw] < Rmf[k + 1][Rw]:  # Lw>(k)Rw
  199.                     LgtR = 1
  200.                 elif Rmf[k + 1][Lw] > Rmf[k + 1][Rw]:  # Lw<(k)Rw
  201.                     LltR = 1
  202.                 else:  # Lw~(k)Rw
  203.                     LeqR = 1
  204.             if (LgtR == 1) and (LltR == 1): #μi~μj
  205.                 join = [0] * M # μi ∨ μj
  206.                 meet = [0] * M # μi ∧ μj
  207.                 for k in range(M):
  208.                     Lw = int(StableMatch[i][k])
  209.                     Rw = int(StableMatch[j][k])
  210.                     if Rmf[k + 1][Lw] < Rmf[k + 1][Rw]:  # Lw>(k)Rw
  211.                         join[k] = Lw
  212.                         meet[k] = Rw
  213.                     elif Rmf[k + 1][Lw] >= Rmf[k + 1][Rw]:  # Lw<(k)Rw
  214.                         join[k] = Rw
  215.                         meet[k] = Lw
  216.                 ij_join = StableMatch.index(tuple(join))
  217.                 ij_meet = StableMatch.index(tuple(meet))
  218.                 print("μ{} ~ {} = μ{}, μ{} ∨ μ{} = {} = μ{}, μ{} ∧ μ{} = {} = μ{}.".format(i,StableMatch[j],j, i,j,join,ij_join, i,j,meet,ij_meet))
  219.             elif (LgtR == 1) and (LltR == 0):
  220.                 print("μ{} ≧ {} = μ{}".format(i,StableMatch[j],j))
  221.             elif (LgtR == 0) and (LltR == 1):
  222.                 print("μ{} ≦ {} = μ{}".format(i,StableMatch[j],j))
  223.             else:
  224.                 print("Error!")
  225.         else:
  226.             print("μ{} = {} = μ{}".format(i,StableMatch[j],j))
  227.  
  228. duration = time.time() - start_time
  229. print(" ")
  230. print('Running time=',format(duration),'s')
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top