安定結婚問題とは(wikipediaより)
安定結婚問題（あんていけっこんもんだい）は安定マッチング問題の 1 つで、D. Gale（デイヴィッド・ゲール）と L. S. Shapley（ロイド・シャプレイ）によって1962年に提唱された問題である。
安定結婚問題の例題は N 人の男性と N 人の女性、および、各個人の希望リストからなる。希望リストとは各個人の好みに基づき異性全員を全順序で並べたリストである。安定結婚問題の解は安定なマッチングである。安定結婚問題の例題に対し、互いに現在組んでいる相手よりも好きであるペア（以下ブロッキングペアとする）が存在しないマッチングを安定なマッチングという。
https://ja.wikipedia.org/wiki/%E5%AE%89%E5%AE%9A%E7%B5%90%E5%A9%9A%E5%95%8F%E9%A1%8C
コード
Gale-Shapleyアルゴリズムで実装した。
# coding: utf-8
# Here your code !
import random
class Message:
def __init__(self,message_list):
self.message_list = message_list
def get_message(self):
return self.message_list[random.randint(0,len(self.message_list)-1)]
class ProposalMessage(Message):
def __init__(self,man_id,woman_id):
self.man_id = man_id
self.woman_id = woman_id
proposal_messages = [
'I love you the most in the world!',
"I need you! I can't live without you!",
"All I need is you!",
"Please make me the happinest man in the world!",
"It is similar to die if I can't marry you!"
]
message_list = map(lambda x: "%s %s" % (x, "Will you marry me?"), proposal_messages)
Message.__init__(self,message_list)
def get_man_id(self):
return self.man_id
def get_woman_id(self):
return self.woman_id
class RejectMessage(Message):
def __init__(self):
reject_messages = [
'I like you. However I regard you as a brother.',
"However I think we need more time to know each other. It is too early to response to your proposal.",
"I'm sorry, I can't consider about marrige for now.",
"I'm sorry, I need a bit of time to consider."
]
message_list = map(lambda x: "%s %s" % ("I appreciate your proposal.", x), reject_messages)
Message.__init__(self,message_list)
def get_conclution(self):
return False
class AcceptMessage(Message):
def __init__(self, left_man_id):
self.left_man_id = left_man_id
accept_messages = [
"I'm happy to hear that. I've just though to marry you too",
"I have the happinest day since I was born!",
"What great day!",
"Sure! All I need is you too!",
"I have dreamed today several times."
]
message_list = map(lambda x: "%s %s" % ("WOW!", x), accept_messages)
Message.__init__(self,message_list)
def get_conclution(self):
return True
def left_from(self):
return self.left_man_id
class MessageAfterRejected(Message):
def __init__(self):
messages_after_rejected = [
"But I'll never forget her. She gave me a lot of happy memories...",
"I need more beer...",
"I can't sleep without wine....",
"........."
]
message_list = map(lambda x: "%s %s" % ("...", x), messages_after_rejected)
Message.__init__(self,message_list)
class MessageAfterRejecting(Message):
def __init__(self):
message_list = [
"How terrible day today! The strange man made me irritate.",
"I wonder that he has seen a mirror.",
"Beautifulness is guilty.",
"I was surprised that he thought that there is possibility to marry me.",
"What makes him foolish?"
]
Message.__init__(self,message_list)
class MessageAfterAccepted(Message):
def __init__(self):
messages_after_accepted = [
"I'm the happinest man in the world!",
"I have to work harder after this.",
"I wonder I'm dreaming now!"
]
message_list = map(lambda x: "%s %s" % ("Hooray!", x), messages_after_accepted)
Message.__init__(self,message_list)
class Man:
def __init__(self,name,man_id,women):
self.name = name
self.man_id = man_id
self.women = women
self.engaged = -1
def propose(self):
return ProposalMessage(self.man_id,self.women.pop(0))
def is_single(self):
return self.engaged == -1
def engage(self,woman_id):
self.engaged = woman_id
return MessageAfterAccepted().get_message()
def broken(self):
self.engaged = -1
return MessageAfterRejected().get_message()
class Woman:
def __init__(self,name,woman_id,men):
self.name = name
self.men = men
self.engaged = -1
def response(self,message):
man_id = message.get_man_id()
if self.engaged == -1:
self.engaged = man_id
return AcceptMessage(-1)
elif self.men.index(man_id) < self.men.index(self.engaged):
left_man_id = self.engaged
self.engaged = man_id
return AcceptMessage(left_man_id)
else:
return RejectMessage()
def after_rejecting(self):
return MessageAfterRejecting().get_message()
def shuffle(cards,shuffle_count):
for i in range(shuffle_count):
card = cards.pop(random.randint(0,len(cards)-1))
cards += [card]
return cards
if __name__ == '__main__':
men_name = shuffle(['Alex','Bob','Chris','Daniel','Edgar','Frank','Geoff'],100)
women_name = shuffle(['Alice','Barbara','Charlotte','Dolly','Elisabeth','Flora','Gloriana'],100)
N = len(men_name)
men_list, women_list = [], []
for i, man in enumerate(men_name):
men_list.append(Man(man,i,shuffle(range(N),100)))
for i, woman in enumerate(women_name):
women_list.append(Woman(woman,i,shuffle(range(N),100)))
cotinue_flag = True
while cotinue_flag:
cotinue_flag = False
for man in men_list:
if man.is_single():
print "#" * 60
cotinue_flag = True
message = man.propose()
print "%s said '%s'" % (man.name, message.get_message())
woman = women_list[message.get_woman_id()]
response = woman.response(message)
print "%s responsed '%s'" % (woman.name, response.get_message())
if response.get_conclution():
print "%s got exciting and said '%s'" % (man.name, man.engage(message.get_woman_id()))
if response.left_from() != -1:
left_man = men_list[response.left_from()]
print "%s got shoked and said '%s'" % ( left_man.name, left_man.broken())
else:
print "%s got shoked and said '%s'" % ( man.name, man.broken())
print "%s twittered '%s'" % (woman.name, woman.after_rejecting())
print "#" * 60
for man in men_list:
print "%s engaged with %s" % ( man.name, women_list[man.engaged].name )
実行結果
悲喜交々が感じられた。
※英語はかなりやっつけで書いた。
############################################################
Daniel said 'I love you the most in the world! Will you marry me?'
Elisabeth responsed 'WOW! I have dreamed today several times.'
Daniel got exciting and said 'Hooray! I have to work harder after this.'
############################################################
Alex said 'It is similar to die if I can't marry you! Will you marry me?'
Elisabeth responsed 'WOW! I have the happinest day since I was born!'
Alex got exciting and said 'Hooray! I'm the happinest man in the world!'
Daniel got shoked and said '... I can't sleep without wine....'
############################################################
Edgar said 'All I need is you! Will you marry me?'
Charlotte responsed 'WOW! Sure! All I need is you too!'
Edgar got exciting and said 'Hooray! I'm the happinest man in the world!'
############################################################
Geoff said 'Please make me the happinest man in the world! Will you marry me?'
Gloriana responsed 'WOW! I have the happinest day since I was born!'
Geoff got exciting and said 'Hooray! I'm the happinest man in the world!'
############################################################
Chris said 'I love you the most in the world! Will you marry me?'
Gloriana responsed 'WOW! What great day!'
Chris got exciting and said 'Hooray! I wonder I'm dreaming now!'
Geoff got shoked and said '... .........'
############################################################
Frank said 'I love you the most in the world! Will you marry me?'
Alice responsed 'WOW! I have dreamed today several times.'
Frank got exciting and said 'Hooray! I'm the happinest man in the world!'
############################################################
Bob said 'I need you! I can't live without you! Will you marry me?'
Alice responsed 'WOW! Sure! All I need is you too!'
Bob got exciting and said 'Hooray! I wonder I'm dreaming now!'
Frank got shoked and said '... I need more beer...'
############################################################
Daniel said 'It is similar to die if I can't marry you! Will you marry me?'
Alice responsed 'WOW! Sure! All I need is you too!'
Daniel got exciting and said 'Hooray! I'm the happinest man in the world!'
Bob got shoked and said '... I can't sleep without wine....'
############################################################
Geoff said 'I love you the most in the world! Will you marry me?'
Elisabeth responsed 'I appreciate your proposal. However I think we need more time to know each other. It is too early to response to your proposal.'
Geoff got shoked and said '... But I'll never forget her. She gave me a lot of happy memories...'
Elisabeth twittered 'I wonder that he has seen a mirror.'
############################################################
Frank said 'I need you! I can't live without you! Will you marry me?'
Gloriana responsed 'I appreciate your proposal. I like you. However I regard you as a brother.'
Frank got shoked and said '... I need more beer...'
Gloriana twittered 'How terrible day today! The strange man made me irritate.'
############################################################
Bob said 'It is similar to die if I can't marry you! Will you marry me?'
Elisabeth responsed 'WOW! What great day!'
Bob got exciting and said 'Hooray! I have to work harder after this.'
Alex got shoked and said '... But I'll never forget her. She gave me a lot of happy memories...'
############################################################
Alex said 'All I need is you! Will you marry me?'
Gloriana responsed 'WOW! I have dreamed today several times.'
Alex got exciting and said 'Hooray! I'm the happinest man in the world!'
Chris got shoked and said '... I need more beer...'
############################################################
Geoff said 'I love you the most in the world! Will you marry me?'
Barbara responsed 'WOW! Sure! All I need is you too!'
Geoff got exciting and said 'Hooray! I wonder I'm dreaming now!'
############################################################
Chris said 'I need you! I can't live without you! Will you marry me?'
Elisabeth responsed 'I appreciate your proposal. However I think we need more time to know each other. It is too early to response to your proposal.'
Chris got shoked and said '... .........'
Elisabeth twittered 'I wonder that he has seen a mirror.'
############################################################
Frank said 'I love you the most in the world! Will you marry me?'
Elisabeth responsed 'I appreciate your proposal. However I think we need more time to know each other. It is too early to response to your proposal.'
Frank got shoked and said '... I can't sleep without wine....'
Elisabeth twittered 'I wonder that he has seen a mirror.'
############################################################
Chris said 'I need you! I can't live without you! Will you marry me?'
Charlotte responsed 'WOW! What great day!'
Chris got exciting and said 'Hooray! I'm the happinest man in the world!'
Edgar got shoked and said '... I can't sleep without wine....'
############################################################
Frank said 'Please make me the happinest man in the world! Will you marry me?'
Barbara responsed 'I appreciate your proposal. I like you. However I regard you as a brother.'
Frank got shoked and said '... I need more beer...'
Barbara twittered 'Beautifulness is guilty.'
############################################################
Edgar said 'I need you! I can't live without you! Will you marry me?'
Flora responsed 'WOW! I'm happy to hear that. I've just though to marry you too'
Edgar got exciting and said 'Hooray! I have to work harder after this.'
############################################################
Frank said 'I need you! I can't live without you! Will you marry me?'
Dolly responsed 'WOW! I have dreamed today several times.'
Frank got exciting and said 'Hooray! I wonder I'm dreaming now!'
############################################################
Daniel engaged with Alice
Alex engaged with Gloriana
Edgar engaged with Flora
Geoff engaged with Barbara
Chris engaged with Charlotte
Frank engaged with Dolly
Bob engaged with Elisabeth