J'ai essayé d'exprimer de la tristesse et de la joie face au problème du mariage stable.

Quel est le problème du mariage stable (de wikipedia)

Le problème du mariage stable est l'un des problèmes d'appariement stable, proposé en 1962 par D. Gale et L. S. Shapley. Un exemple de problème de mariage stable consiste en N hommes et N femmes, et une liste de souhaits pour chaque individu. La liste de souhaits est une liste dans laquelle tous les sexes opposés sont classés dans l'ordre complet en fonction des préférences de chaque individu. La solution au problème du mariage stable est l'appariement stable. Contrairement à l'exemple du problème du mariage stable, l'appariement dans lequel il n'y a pas de paire (appelée ci-après paire de blocage) que l'on aime plus que l'autre partie actuellement en formation est appelé appariement stable. https://ja.wikipedia.org/wiki/%E5%AE%89%E5%AE%9A%E7%B5%90%E5%A9%9A%E5%95%8F%E9%A1%8C

code

Implémenté avec l'algorithme 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 )

Résultat d'exécution

J'ai ressenti de la tristesse.

############################################################
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

Recommended Posts

J'ai essayé d'exprimer de la tristesse et de la joie face au problème du mariage stable.
J'ai essayé de résoudre le problème avec Python Vol.1
J'ai essayé de sauvegarder les données avec discorde
J'ai essayé d'apprendre l'angle du péché et du cos avec le chainer
J'ai essayé de mettre en œuvre le problème du voyageur de commerce
J'ai essayé de contrôler la bande passante et le délai du réseau avec la commande tc
[Introduction à AWS] J'ai essayé de porter une application de conversation et de jouer avec text2speech @ AWS ♪
J'ai essayé d'entraîner la fonction péché avec chainer
J'ai essayé de lire et d'enregistrer automatiquement avec VOICEROID2 2
J'ai essayé d'implémenter et d'apprendre DCGAN avec PyTorch
J'ai essayé de toucher un fichier CSV avec Python
J'ai essayé de résoudre Soma Cube avec python
J'ai essayé de lire et d'enregistrer automatiquement avec VOICEROID2
J'ai essayé d'implémenter Grad-CAM avec keras et tensorflow
J'ai essayé de résoudre le problème d'optimisation du placement de la machine virtuelle (version simple) avec blueqat
J'ai essayé d'automatiser la mise à jour de l'article du blog Livedoor avec Python et sélénium.
J'ai essayé de comparer la vitesse de traitement avec dplyr de R et pandas de Python
Le 15e temps réel hors ligne, j'ai essayé de résoudre le problème de l'écriture avec python
J'ai essayé de prédire et de soumettre les survivants du Titanic avec Kaggle
J'ai essayé de trouver l'entropie de l'image avec python
J'ai essayé de simuler la propagation de l'infection avec Python
J'ai essayé d'analyser les émotions de tout le roman "Weather Child" ☔️
J'ai essayé de trouver la moyenne de plusieurs colonnes avec TensorFlow
J'ai essayé de notifier les informations de retard de train avec LINE Notify
J'ai essayé de résoudre le problème d'optimisation des combinaisons avec Qiskit
J'ai essayé d'illustrer le temps et le temps du langage C
J'ai essayé d'afficher l'heure et la météo d'aujourd'hui w
J'ai essayé d'énumérer les différences entre java et python
J'ai essayé de créer une interface graphique à trois yeux côte à côte avec Python et Tkinter
J'ai essayé de publier automatiquement sur ChatWork au moment du déploiement avec Fabric et ChatWork Api
J'ai essayé de résoudre le problème de F02 comment écrire en temps réel hors ligne avec Python
J'ai aussi essayé d'imiter la fonction monade et la monade d'état avec le générateur en Python
J'ai essayé de déplacer le ballon
J'ai essayé d'estimer la section.
J'ai essayé de décrire le trafic en temps réel avec WebSocket
J'ai essayé de résoudre l'édition du débutant du livre des fourmis avec python
J'ai essayé d'automatiser l'arrosage du pot avec Raspberry Pi
J'ai essayé de visualiser les signets volant vers Slack avec Doc2Vec et PCA
J'ai essayé de traiter l'image en "style croquis" avec OpenCV
J'ai essayé de faire un processus d'exécution périodique avec Selenium et Python
J'ai essayé de démarrer avec Bitcoin Systre le week-end
Je voulais résoudre le problème ABC164 A ~ D avec Python
J'ai essayé de créer des taureaux et des vaches avec un programme shell
J'ai essayé de traiter l'image dans un "style de dessin au crayon" avec OpenCV
J'ai essayé d'agrandir la taille du volume logique avec LVM
J'ai essayé de détecter facilement les points de repère du visage avec python et dlib
J'ai essayé de résoudre le problème de planification des équipes par diverses méthodes
J'ai essayé d'améliorer l'efficacité du travail quotidien avec Python
J'ai essayé de créer un traitement par lots sans serveur pour la première fois avec DynamoDB et Step Functions
J'ai essayé d'implémenter Autoencoder avec TensorFlow
J'ai essayé de résumer la commande umask
J'ai essayé de visualiser AutoEncoder avec TensorFlow
J'ai essayé de reconnaître le mot de réveil
J'ai essayé de résumer la modélisation graphique.
J'ai essayé d'estimer le rapport de circonférence π de manière probabiliste
J'ai essayé de toucher l'API COTOHA
Python: j'ai essayé le problème du voyageur de commerce
J'ai essayé d'implémenter CVAE avec PyTorch
J'ai essayé de jouer avec l'image avec Pillow