In [1]:

    

#なるほどね
men=['a','b','c']
women=['d','e','f']
pref={'a':['d','e','f'],'b':['e','d','f'],'c':['d','e','f'],'d':['b','a','c'],'e':['a','b','c'],'f':['a','b','c']}
for n in pref:
        pref[n].reverse()
rank={'d':{'a':2,'b':1,'c':3},'e':{'a':1,'b':2,'c':3},'f':{'a':1,'b':2,'c':3}}
freemen=list(men)
numpart=len(men)
S={}
while freemen:
    m=freemen.pop()
    if len(pref[m])==0:
        continue
    w=pref[m].pop()
    if w not in S:
        S[w]=m
    else:
        mprime=S[w]
        if rank[w][m]<rank[w][mprime]:
            S[w]=m
            freemen.append(mprime)
        else:
            freemen.append(m)
print S


    

    




{'e': 'b', 'd': 'a', 'f': 'c'}

In [3]:

    

list=['a','b']


    

In [ ]:

    




    

In [8]:

    

men.pop()


    

    
Out[8]:





'c'

In [1]:

    

#deferred acceptance function
#a　男リスト
#c　preference list
#d　女の男ランク
def da(a,c,d):
    for n in c:
        c[n].reverse()
    freemen=list(a)
    numpart=len(a)
    S={}
    while freemen:
        m=freemen.pop()
        if len(c[m])==0:
            continue
        w=c[m].pop()
        if w not in S:
            S[w]=m
        else:
            mprime=S[w]
            if d[w][m]<d[w][mprime]:
                S[w]=m
                freemen.append(mprime)
            else:
                freemen.append(m)
    print S


    

In [2]:

    

a=['a','b','c']
c={'a':['d','e','f'],'b':['e','d','f'],'c':['d','e','f'],'d':['b','a','c'],'e':['a','b','c'],'f':['a','b','c']}
d={'d':{'a':2,'b':1,'c':3},'e':{'a':1,'b':2,'c':3},'f':{'a':1,'b':2,'c':3}}
da(a,c,d)


    

    




{'e': 'b', 'd': 'a', 'f': 'c'}

In [ ]:

    

range(1,3)


    

In [1]:

    

#引数をpref（順序付き）と人数
# a={'a':{1:'d',2:'e',3:'f'},'b':{1:'e',2:'d',3:'f'},'c':{1:'d',2:'e',3:'f'}}
#b={'d':{1:'b',2:'a',3:'c'},'e':{1:'a',2:'b',3:'c'},'f':{1:'a',2:'b',3:'c'}}
#c=3
def da2(a,b,c):
    S={}
    free=[]
    for i in a:
        free.append(i)
    n=1
    while free:
        m=free.pop()
        f=a[m][n]
        if f not in S:
            S[f]=m
        else:
            l=S[f]
            for j in range(1,c+1):
                if b[f][j]==m:
                    d=j
                else: continue
            for k in range(1,c+1):
                if b[f][k]==l:
                    e=k
                else: continue
            if e<d:
                free.append(m)
                n+=1
            else:
                S[f]=m
                free.append(l)
                n+=1
        if len(free)==0:
            return S


    

In [55]:

    

a={'a':{1:'d',2:'e',3:'f'},'b':{1:'e',2:'d',3:'f'},'c':{1:'d',2:'e',3:'f'}}
b={'d':{1:'b',2:'a',3:'c'},'e':{1:'a',2:'b',3:'c'},'f':{1:'a',2:'b',3:'c'}}


    

In [3]:

    

da2(a,b,c)


    

    




---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-3-bba94a40e676> in <module>()
----> 1 da2(a,b,c)

NameError: name 'c' is not defined

In [56]:

    

#引数をpref（順序付き）と人数
#男プロポーズと女プロポーズの結果を同時に表示
# a={'a':{1:'d',2:'e',3:'f'},'b':{1:'e',2:'d',3:'f'},'c':{1:'d',2:'e',3:'f'}}
#b={'d':{1:'b',2:'a',3:'c'},'e':{1:'a',2:'b',3:'c'},'f':{1:'a',2:'b',3:'c'}}
#c=3
def da2(a,b):
    S={}
    free=[]
    T={}
    wfree=[]
    for i in a:
        free.append(i)
    for i in b:
        wfree.append(i)
    c=len(free)
    n=1
    while free:
        m=free.pop()
        f=a[m][n]
        if f not in S:
            S[f]=m
        else:
            l=S[f]
            for j in range(1,c+1):
                if b[f][j]==m:
                    d=j
                else: continue
            for k in range(1,c+1):
                if b[f][k]==l:
                    e=k
                else: continue
            if e<d:
                free.append(m)
                n+=1
            else:
                S[f]=m
                free.append(l)
                n+=1
        if len(free)==0: continue
    g=1
    while wfree:
        m=wfree.pop()
        f=b[m][g]
        if f not in T:
            T[f]=m
        else:
            l=T[f]
            for j in range(1,c+1):
                if a[f][j]==m:
                    d=j
                else: continue
            for k in range(1,c+1):
                if a[f][k]==l:
                    e=k
                else: continue
            if e<d:
                wfree.append(m)
                g+=1
            else:
                T[f]=m
                wfree.append(l)
                g+=1
        if len(wfree)==0:
            return S,T


    

In [57]:

    

da2(a,b)


    

    
Out[57]:





({'d': 'a', 'e': 'b', 'f': 'c'}, {'a': 'e', 'b': 'd', 'c': 'f'})

In [17]:

    

x={1:{'a':'b','c':'d'}}
y={2:{'e':'f'}}


    

In [19]:

    

x.update(y)


    

In [20]:

    

x


    

    
Out[20]:





{1: {'a': 'b', 'c': 'd'}, 2: {'e': 'f'}}

In [34]:

    

a={'x':1,'y':8,'z':2}
b={'x':5,'y':10,'z':7}
c={'x':6,'y':1,'z':10}
d={'x':9,'y':9,'z':10}
e={'x':6,'y':6,'z':2}
f={'x':8,'y':3,'z':4}
g={'x':2,'y':5,'z':5}
h={'x':7,'y':4,'z':8}
i={'x':4,'y':10,'z':6}
j={'x':3,'y':7,'z':9}


    

In [35]:

    

x=[]
y=[]
z=[]


    

In [36]:

    

w=[a,b,c,d,e,f,g,h,i,j]


    

In [49]:

    

S={}
for l in w:
    n=[]
    m=['x','y','z']
    for k in m:
        n.append(l[k])
    o=max(n)
    for p in m:
        if l[p]==o:
            S[str(l)]=p


    

In [50]:

    

S


    

    
Out[50]:





{"{'y': 1, 'x': 6, 'z': 10}": 'z',
 "{'y': 10, 'x': 4, 'z': 6}": 'y',
 "{'y': 10, 'x': 5, 'z': 7}": 'y',
 "{'y': 3, 'x': 8, 'z': 4}": 'x',
 "{'y': 4, 'x': 7, 'z': 8}": 'z',
 "{'y': 5, 'x': 2, 'z': 5}": 'z',
 "{'y': 6, 'x': 6, 'z': 2}": 'y',
 "{'y': 7, 'x': 3, 'z': 9}": 'z',
 "{'y': 8, 'x': 1, 'z': 2}": 'y',
 "{'y': 9, 'x': 9, 'z': 10}": 'z'}

In [1]:

    

#データ構造は以下のとおり
#ｍ：numberof males
#n:number of females
#maless:[0,1///m-1]
#females:[0,1,///n-1]
#m_pref:二次元配列m*(n+1)
#f_pref:二次元配列n*(m+1)
#m_pref[i]=[0,1,2///n(unmatch)]
#f_prefも同様の順列で表記
#出力は、1次元のm_matched:長さがmのmatch相手を並べた順列
#一回誰かに取られたら-1で置き換える。


    

In [54]:

    

import numpy as np
m=np.arange(5)
n=np.arange(8)


    

In [55]:

    

m


    

    
Out[55]:





array([0, 1, 2, 3, 4])

In [56]:

    

n


    

    
Out[56]:





array([0, 1, 2, 3, 4, 5, 6, 7])

In [57]:

    

a=np.random.permutation(9)
b=np.random.permutation(9)
c=np.random.permutation(9)
d=np.random.permutation(9)
e=np.random.permutation(9)


    

In [58]:

    

m_pref=np.vstack((a,b,c,d,e))


    

In [59]:

    

f=np.random.permutation(6)
g=np.random.permutation(6)
h=np.random.permutation(6)
i=np.random.permutation(6)
j=np.random.permutation(6)
k=np.random.permutation(6)
l=np.random.permutation(6)
o=np.random.permutation(6)


    

In [60]:

    

n_pref=np.vstack((f,g,h,i,j,k,l,o))


    

In [8]:

    

n_pref


    

    
Out[8]:





array([[3, 5, 0, 1, 2, 4],
       [3, 2, 4, 1, 5, 0],
       [2, 3, 0, 4, 5, 1],
       [2, 4, 0, 3, 1, 5],
       [3, 1, 5, 4, 2, 0],
       [1, 3, 4, 0, 5, 2],
       [1, 5, 2, 3, 0, 4],
       [1, 2, 3, 5, 0, 4]])

In [9]:

    

m_pref


    

    
Out[9]:





array([[1, 0, 5, 8, 3, 4, 7, 2, 6],
       [6, 2, 8, 0, 1, 3, 5, 4, 7],
       [6, 5, 7, 2, 0, 3, 8, 4, 1],
       [4, 7, 5, 6, 8, 1, 3, 0, 2],
       [8, 3, 4, 0, 7, 6, 2, 1, 5]])

In [14]:

    

#データ形式調整済み。
#女性の選好：n_pref
#男性の選好：m_pref
#男性5人女性8人のマッチング
#unmatchは8で表記
S=[]
n=1
free=range(5)
while free:
    m=free.pop()
    f=m_pref[m,:][n]
    if f not in S:
        S.append(f)
    elif f==8:
        S.append(f)
    else:
        l=S.index(f)
        for j in range(6):
            if n_pref[f,:][j]==m:
                d=j
            else: continue
        for k in range(6):
            if n_pref[f,:][k]==l:
                e=k
            else: continue
        if e<d:
            free.append(m)
            n+=1
        else:
            S.append(m)
            S.pop(l)
            S.insert(l,-1)
            free.append(l)
            n+=1
if len(free)==0:
    S.reverse()
    print S


    

    




[0, 2, 5, 7, 3]

In [13]:

    

# 修正案
#5があったらもう5を入れちゃう
S=[]
n=1
free=range(5)
while free:
    m=free.pop()
    f=m_pref[m,:][n]
    if f not in S:
        S.append(f)
    elif f==8:
        S.append(f)
    else:
        if -1 in S:
            l=-1
        else:
            l=S.index(f)
        for j in range(6):
            if n_pref[f,:][j]==m:
                d=j
            else: continue
        for k in range(6):
            if n_pref[f,:][k]==l:
                e=k
            else: continue
        for p in range(6):
            if n_pref[f,:][p]==5:
                
        if e<d:
            free.append(m)
            n+=1
        else:
            S.append(m)
            S.pop(l)
            S.insert(l,-1)
            free.append(l)
            n+=1
if len(free)==0:
    S.reverse() # 修正1
    print S  #修正2


    

    




[0, 2, 5, 7, 3]

In [49]:

    

m_pref


    

    
Out[49]:





array([[7, 3, 1, 2, 8, 4, 5, 6, 0],
       [7, 0, 6, 3, 4, 8, 5, 1, 2],
       [1, 8, 4, 0, 6, 2, 5, 3, 7],
       [1, 0, 7, 4, 2, 6, 3, 8, 5],
       [8, 1, 3, 4, 2, 6, 0, 7, 5]])

In [50]:

    

n_pref


    

    
Out[50]:





array([[4, 2, 1, 3, 5, 0],
       [2, 4, 1, 3, 5, 0],
       [0, 4, 2, 3, 5, 1],
       [0, 5, 4, 3, 1, 2],
       [5, 2, 1, 4, 3, 0],
       [1, 4, 3, 5, 2, 0],
       [4, 0, 5, 1, 3, 2],
       [1, 4, 3, 2, 0, 5]])

In [51]:

    

#修正版
S=np.tile([-1],5)
free=range(5)


    

In [52]:

    

S


    

    
Out[52]:





array([-1, -1, -1, -1, -1])

In [53]:

    

free


    

    
Out[53]:





[0, 1, 2, 3, 4]

In [54]:

    

#最新版
#nのカウントをリセットする仕組みを加えた。
#多分あってるはずです。関数化は明日やります。
n=0
while free:
    A=free.pop() 
    F=m_pref[A,:][n]
    if F not in S:
        S[A]=F
        n=0        #nをリセット
    elif F==8:
        S[A]=8
    else:
        for y in range(5):
            if S[y]==F:
                M=y #MはFがいる場所のindex
        for z in range(6):
            if n_pref[F,:][z]==M:
                Z=z
            if n_pref[F,:][z]==A:
                W=z
            if n_pref[F,:][z]==5:
                V=z
        if V<W and V<Z:
            S[M]=-1
            free.append(A)    
            free.append(M)
            n+=1
        elif W<Z and W<V:
            S[A]=F
            S[M]=-1
            free.append(M)
            n+=1
        elif Z<W and Z<V:
            free.append(A)
            n+=1
    if len(free)==0:
        print S


    

    




[3 7 1 0 8]

In [1]:

    

import numpy as np
g=np.array([[1,2,3],[4,5,6],[7,8,9],[10,11,12]])


    

In [3]:

    

g.shape[0]


    

    
Out[3]:





4

In [10]:

    

#そもそもアンマッチの場合を修正しました。
#出力が男女の結果となるように修正しました。
#Pがm_pref
#Qがn_pref
def da3(P,Q):
    N=P.shape[0]
    G=Q.shape[0]
    S=np.tile([-1],N)
    free=range(N)
    n=0
    while free:
        A=free.pop() 
        F=P[A,:][n]
        if F==G:
            S[A]=G
        else:
            for J in range(N+1):   #そもそもマッチしない場合を追加
                if Q[F,:][J]==A:
                    D=J
                if Q[F,:][J]==N:
                    E=J
            if E<D:
                free.append(A)
                n+=1
            else:
                if F not in S:
                    S[A]=F
                    n=0        #nをリセット
                else:
                    for y in range(N):
                        if S[y]==F:
                            M=y         #MはFがいる場所のindex
                    for z in range(N+1):
                        if Q[F,:][z]==M:
                            Z=z
                        if Q[F,:][z]==A:
                            W=z
                    if W<Z:
                        S[A]=F
                        S[M]=-1
                        free.append(M)
                        n+=1
                    else:
                        free.append(A)
                        n+=1
                if len(free)==0:   #女性の結果も表示するように修正
                    s=list(S)
                    L=np.tile([N],G)
                    l=list(L)
                    for u in s:
                        if u==G: continue  #アンマッチの時はスルー
                        else:
                            v=s.index(u)
                            l[u]=v
                    return s,l


    

In [64]:

    

da3(m_pref,n_pref)


    

    
Out[64]:





([7, 5, 6, 0, 8], [3, 5, 5, 5, 5, 1, 2, 0])

In [46]:

    

m_pref


    

    
Out[46]:





array([[6, 7, 2, 3, 4, 8, 5, 0, 1],
       [5, 8, 6, 1, 4, 3, 7, 0, 2],
       [7, 8, 2, 5, 4, 1, 6, 3, 0],
       [4, 6, 8, 2, 1, 7, 5, 0, 3],
       [6, 7, 4, 8, 5, 2, 3, 1, 0]])

In [47]:

    

n_pref


    

    
Out[47]:





array([[1, 3, 2, 4, 5, 0],
       [3, 1, 0, 4, 2, 5],
       [3, 5, 2, 1, 4, 0],
       [2, 3, 5, 4, 0, 1],
       [2, 5, 0, 1, 3, 4],
       [3, 2, 4, 0, 1, 5],
       [3, 0, 5, 4, 1, 2],
       [3, 5, 1, 2, 0, 4]])

In [2]:

    

import numpy as np
a=np.arange(5)


    

In [3]:

    

a


    

    
Out[3]:





array([0, 1, 2, 3, 4])

In [4]:

    

A=list(a)


    

In [5]:

    

A.index(0)


    

    
Out[5]:





0

In [7]:

    

A


    

    
Out[7]:





[0, 1, 2, 3, 4]

In [8]:

    

b=np.array(A)


    

In [1]:

    

b


    

    




---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-1-3b5d5c371295> in <module>()
----> 1 b

NameError: name 'b' is not defined

In [76]:

    

import numpy as np


    

In [77]:

    

a=np.random.permutation(6)
b=np.random.permutation(6)
c=np.random.permutation(6)
d=np.random.permutation(6)
e=np.random.permutation(6)


    

In [78]:

    

f=np.random.permutation(9)
g=np.random.permutation(9)
h=np.random.permutation(9)
i=np.random.permutation(9)
j=np.random.permutation(9)
k=np.random.permutation(9)
l=np.random.permutation(9)
o=np.random.permutation(9)


    

In [79]:

    

m_pref=np.vstack((a,b,c,d,e))


    

In [80]:

    

n_pref=np.vstack((f,g,h,i,j,k,l,o))


    

In [81]:

    

m_pref


    

    
Out[81]:





array([[0, 5, 1, 3, 4, 2],
       [4, 2, 0, 1, 3, 5],
       [5, 1, 3, 2, 4, 0],
       [1, 0, 5, 3, 2, 4],
       [0, 1, 3, 5, 4, 2]])

In [82]:

    

n_pref


    

    
Out[82]:





array([[4, 2, 1, 7, 6, 3, 8, 5, 0],
       [1, 7, 8, 3, 5, 0, 6, 4, 2],
       [1, 5, 2, 6, 3, 7, 8, 4, 0],
       [5, 1, 6, 2, 7, 8, 4, 3, 0],
       [2, 6, 4, 8, 5, 3, 7, 1, 0],
       [3, 2, 6, 4, 8, 5, 7, 1, 0],
       [3, 6, 4, 0, 5, 2, 7, 8, 1],
       [0, 2, 3, 8, 5, 6, 1, 4, 7]])

In [83]:

    

def da3(P,Q):
    import sys
    
    if isinstance(Q, list) != True and isinstance(Q,np.ndarray) != True:
        print "Input Error!!"
        sys.exit()
        
    if isinstance(P, list):
        P = np.array(P)
        Q = np.array(Q)
    elif isinstance(P, np.ndarray):
        print "ndarray"
    else:
        print "Input Error!!"
        sys.exit()
    N=P.shape[0]
    G=Q.shape[0]
    S=np.tile([-1],N)
    free=range(N)
    n=0
    
    while free:
        # print S
        """
        上のシャープを外すことで男性の婚約状況の一周ごとの推移を表示することができます
        正しくない結果が返ってきている疑いのある時に様子を見るため使いましょう
        """
        A=free.pop() 
        F=P[A,:][n]
        if F==G:
            S[A]=G
        else:
            for J in range(N+1):   
                if Q[F,:][J]==A:
                    D=J
                if Q[F,:][J]==N:
                    E=J
            if E<D:
                free.append(A)
                n+=1
            else:
                if F not in S:
                    S[A]=F
                    n=0        
                else:
                    for y in range(N):
                        if S[y]==F:
                            M=y         
                    for z in range(N+1):
                        if Q[F,:][z]==M:
                            Z=z
                        if Q[F,:][z]==A:
                            W=z
                    if W<Z:
                        S[A]=F
                        S[M]=-1
                        free.append(M)
                        n+=1
                    else:
                        free.append(A)
                        n+=1
        if len(free)==0:   
            s=list(S)
            L=np.tile([N],G)
            l=list(L)
            for u in s:
                if u==G: continue  
                else:
                    v=s.index(u)
                    l[u]=v
            return s,l
        else: continue


    

In [84]:

    

da3(m_pref,n_pref)


    

    




ndarray






    




---------------------------------------------------------------------------
UnboundLocalError                         Traceback (most recent call last)
<ipython-input-84-a3aa45e23f2f> in <module>()
----> 1 da3(m_pref,n_pref)

<ipython-input-83-7e20afca38d7> in da3(P, Q)
     36                 if Q[F,:][J]==N:
     37                     E=J
---> 38             if E<D:
     39                 free.append(A)
     40                 n+=1

UnboundLocalError: local variable 'E' referenced before assignment

In [35]:

    

# アルゴリズムがどうにかしているためにうまくいかない例
pl = [[0,1,2],
      [0,2,1]]

pt = [[0,1,2],
      [1,2,0]]
da3(pl,pt)


    

    




[-1 -1]
[-1  0]
[ 0 -1]






    
Out[35]:





([0, 2], [0, 2])