• API
• FAQ
• Tools
• Archive
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]):
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.

Top