[PYTHON] L'histoire de la recherche du n optimal dans N poing

Qu'est-ce que N fist

Quand il y a beaucoup de monde, il est difficile de gagner ou de perdre même si on y joue, et je pense que tout le monde a l'expérience de prendre beaucoup de temps. Si vous faites le tour avec "Valeur attendue de Janken", vous trouverez de nombreux articles, je vais donc omettre l'explication, mais Sur la page Nombre moyen de fois pour décider une personne avec Janken, un gagnant est choisi pour 2 à 50 personnes. Le nombre moyen de fois jusqu'à est indiqué. En regardant cela, quand il y avait 8 personnes, c'était déjà 12,1 fois, dépassant 10 fois.

De cette façon, quand il y a un grand nombre de personnes, il est difficile de rivaliser, mais pour résoudre cela, nous allons considérer N poing.

N-fist est un jeu dans lequel les participants échangent volontairement l'un des N nombres de 0 à (N-1), et la personne qui donne le plus petit nombre est le gagnant. Par exemple, s'il y a 5 participants, l'un des trois nombres jusqu'à 0,2 sera donné, et par conséquent, 2,0,2,1,0 et 1 seront donnés lorsque les nombres seront donnés. Le nombre de personnes est le plus petit, donc la personne qui donne 1 est la gagnante. Avec cette règle, lorsque vous êtes deux personnes, vous ne pouvez jamais gagner ni perdre. Par conséquent, le nombre minimum de personnes est de trois.

D'après mes recherches jusqu'à présent, si N est égal à 3, il semble y avoir quelque chose appelé "gamer janken". Quand N est 5, il semble y avoir quelque chose appelé "Ippatsu Janken". Aussi, au début, j'ai nommé ce jeu "plusieurs poings", mais il semble qu'il existait à l'époque Meiji par une autre règle. Ensuite, je l'ai nommé "Numerical Fist", qui semble exister en Chine.

Dans cet article, le but de ce N-poing est de calculer la valeur N optimale (c'est-à-dire qu'un gagnant est déterminé par le nombre minimum de fois) lorsqu'il y a p participants. Comme déjà mentionné, si les deux dernières personnes restent, il n'y aura ni victoire ni perte, nous adopterons donc la valeur attendue de 1,5 pour Janken.

Combinaison du nombre de numéros émis

Par exemple, s'il y a 5 participants et N est 3, la main que chaque participant prendra est Ce sera 3 $ ^ 5 $. Cela ressort clairement du fait que la séquence de nombres ternaires de 00000 à 22222 est de 100 000 en ternaire, soit 3 ^ 5 $. Autrement dit, lorsque p personnes sont en concurrence avec N nombres, la séquence de nombres donnée par chaque participant est N^p
Ce sera dans la rue.

De plus, en comptant les nombres de 0, 1 et 2 quant au nombre de personnes qui les ont diffusées, La combinaison est la même que la combinaison de nombres obtenue en multipliant p. Nous appellerons cela un «modèle de résultat» pour votre commodité plus tard.

Par exemple, dans l'exemple ci-dessus

1. 5 personnes donnent le même numéro
2. 4 personnes donnent le même numéro, 1 personne donne un numéro différent
3. 3 personnes donnent le même numéro, 2 personnes donnent des numéros différents
4. 3 personnes donnent le même numéro, 2 personnes donnent des numéros différents
5. Deux personnes donnent le même numéro, deux personnes donnent des numéros différents et une personne donne le numéro restant

Il existe 5 modèles de, mais cela correspond au modèle qui divise 5 en 3 des nombres agrégés.

1. 5 = 5
2. 5 = 4 + 1
3. 5 = 3 + 2
4. 5 = 3 + 1 + 1
5. 5 = 2 + 2 + 1

La valeur attendue est déterminée par «probabilité d'occurrence x valeur lorsqu'elle se produit». En trouvant la probabilité d'occurrence de ce modèle de résultat, la valeur attendue peut être trouvée. Trouver la probabilité d'occurrence d'un modèle de résultat, c'est, en d'autres termes, trouver combien de modèles sont dans ce modèle sur toutes les fois $ N ^ p $.

Valeur attendue à la répétition du jeu

Dans ce jeu, un gagnant n'est pas toujours décidé à la fois. Dans l'exemple ci-dessus, s'il y a une personne qui a donné 1 et une personne qui a donné 2, la personne qui a donné 1 et la personne qui a donné 2 seront les gagnants, et les deux joueront à nouveau au jeu. .. Cependant, dans le cas de deux personnes, il n'y a ni victoire ni défaite, donc la décision finale sera prise par Janken. Dans l'exemple ci-dessus, 4) est ce cas. Dans 3) également, il y a deux gagnants parce que les deux donnent les nombres qui ont été donnés moins.

Si 7 participants rivalisent avec N = 3, par exemple 7=3+2+2
Dans la combinaison de, il y aura 4 gagnants.

Ces gagnants rejoueront le jeu et restreindront les gagnants.

Pour connaître la valeur attendue du nombre de parties à répéter en extrayant ce gagnant, voir l'article Calculer le nombre moyen de fois jusqu'à la fin de Janken. Il y a une explication E_n = \sum_{k=1}^{n} P(n,k)(E_{k}+1)
Sera.

$ E_n $ est la valeur attendue lorsque le nombre de personnes est n, et P (n, k) est la probabilité que k personnes gagnent lorsque le nombre de personnes est n. Cette formule peut être transformée en $ E_n = 1 + \ sum_ {k = 1} ^ {n} P (n, k) E_ {k} $.

Même si vous ne connaissez pas la preuve mathématique de cette formule, si c'est cette formule "La valeur attendue $ E_n $ est ($ E_n = ), essayez-la une fois (1 +), et si le nombre de gagnants est k (P (n, k)) et que vous gagnez plus. Multipliez la valeur attendue de ( E_ {k}) $ et ajoutez les cas de toutes les personnes restantes ($ \ sum_ {k = 1} ^ {n} $) ", donc je pense que c'est facile à comprendre. Je vais.

Tel qu'il est, le terme de k = n est sur le côté droit et $ E_ {n} $ existe à la fois sur les côtés gauche et droit, et si vous construisez la logique telle qu'elle est, ce sera un processus récursif infini. Ce plus loin

E_n = 1 + \sum_{k=1}^{n-1} P(n,k)E_{k} + P(n,n)E_{n}

Transformé et

E_{n} - P(n,n)E_{n}= 1 + \sum_{k=1}^{n-1} P(n,k)E_{k}

(1- P(n,n))E_{n}= 1 + \sum_{k=1}^{n-1} P(n,k)E_{k}

\displaystyle E_{n} = \frac{1 + \sum_{k=1}^{n-1} P(n,k)E_{k}}{(1- P(n,n))}

Ce faisant, vous pourrez trouver la valeur attendue.

Traitement récursif

À partir de maintenant, nous allons créer un processus pour trouver la valeur attendue, mais pendant le processus à partir de maintenant, un traitement récursif apparaîtra plusieurs fois. Le calcul de la valeur inférieure est appelé plusieurs fois à partir de la valeur supérieure, mais c'est une perte de vitesse de traitement pour effectuer exactement le même calcul, donc une fois qu'il est calculé, préparez-en un qui renvoie le résultat du calcul immédiatement à partir de la prochaine fois. Je le ferai.

En outre, pour implémenter ce processus, créez une liste qui ne fait pas d'exception même si vous accédez en dehors de la plage de la liste dans laquelle la valeur est définie.

ExpandList.py

# ------------------------------------------------------------------------------------------------------------
#
#Se développe automatiquement lorsqu'il est accédé en dehors de la liste
#
#M. shiracamus a expliqué comment réaliser en héritant de liste.
#Merci beaucoup.
#Je l'ai réécrit en conséquence.
#
# ------------------------------------------------------------------------------------------------------------
#


class ExpandList(list):
    def __setitem__(self, i, value):
        """
Définir la valeur à la position spécifiée
        Parameters
        ----------
        i :Indice
        value :Valeur à définir
        """
        if i >= len(self):
            self.extend([None] * (i - len(self) + 1))
        super().__setitem__(i, value)

    def __getitem__(self, i):
        """
Récupère la valeur de l'emplacement spécifié
        Parameters
        ----------
        i :Indice

        Returns :
        -------
            (À portée) :Valeur à la position spécifiée
            (Lorsque hors de portée) : None
        """

        return super().__getitem__(i) if i < len(self) else None


class ExpandList2D(ExpandList):
    def __setitem__(self, pos, value):
        """
Définir la valeur à la position spécifiée
        Parameters
        ----------
        pos :Indice
        value :Valeur à définir
        """

        y, x = pos
        if super().__getitem__(y) is None:
            super().__setitem__(y, ExpandList())
        super().__getitem__(y)[x] = value

    def __getitem__(self, pos):
        """
Récupère la valeur de l'emplacement spécifié
        Parameters
        ----------
        pos :Indice
        Returns :
        -------
            (À portée) :Valeur à la position spécifiée
            (Lorsque hors de portée) : None
        """
        y, x = pos
        row = super().__getitem__(y)
        return row and row[x]


if __name__ == '__main__':
    import pprint

    obj = ExpandList()
    obj[3] = 3
    pprint.pprint(obj)
    obj[0] = 1
    pprint.pprint(obj)
    obj[5] = 5
    pprint.pprint(obj)

    print(obj[1])
    print(obj[2])
    print(obj[6])
    print(obj[5])

    print("++++++++++ 2D List+++++++++++")

    obj = ExpandList2D()
    obj[3, 3] = 'a33'
    pprint.pprint(obj)
    obj[2, 0] = 'b20'
    pprint.pprint(obj)
    obj[5, 6] = 'a56'
    pprint.pprint(obj)

    print(obj[3, 3])
    print(obj[2, 0])
    print(obj[2, 1])
    print(obj[6, 1])
    print(obj[5, 6])

Le traitement ci-dessus renvoie None lors de la lecture hors plage pour une liste à 1 dimension et une liste à 2 dimensions, et gets () qui retourne la valeur stockée dans le cas contraire. Si vous spécifiez en dehors de la plage et que vous la stockez, la liste est développée et stockée. ~~ Il n'hérite pas de la liste et n'est pas un itérateur, mais c'est suffisant pour cela, il est donc implémenté de cette manière. ~~

~~ Il s'agit de Python, donc il y a peut-être déjà quelque chose de plus utile, mais je ne l'ai pas trouvé après un certain temps, alors je vais juste l'utiliser. ~~ J'ai reçu un commentaire de @shiracamus et l'ai changé pour hériter de la liste.

Ensuite, créez une classe qui renvoie la valeur enregistrée si elle a déjà été calculée et appelle la méthode de manière récursive si elle n'a pas encore été calculée.

ProcessWithMemory.py

# ------------------------------------------------------------------------------------------------------------
#
#Le traitement une fois calculé renvoie le résultat sans calcul
#
# ------------------------------------------------------------------------------------------------------------
#
from ExpandList import ExpandList2D


class Container:
    def __init__(self):
        """
Conteneur pour stocker des valeurs
        """
        self.value = None

    def get(self):
        """
Obtenez la valeur stockée
        Returns
        -------
Valeur sauvegardée
        """
        return self.value

    def set(self, data):
        """
Enregistrer la valeur
        Parameters
        ----------
        data :Valeur à économiser
        """
        self.value = data


class ProcessWithMemory:
    def __init__(self, function):
        """
Une classe qui renvoie la valeur enregistrée, le cas échéant, et appelle le processus dans le cas contraire
        """
        self.value = ExpandList2D()
        self.check_process = function

    def process(self, i, j, *args):
        """
Vérifie si elle a déjà été calculée, renvoie la valeur si c'est le cas, appelle la méthode enregistrée si non
        Parameters
        ----------
        i :Indice 1ère dimension
        j :Indice 2ème dimension
        kwargs :Argument de longueur variable

        Returns
        -------
Valeur de résultat
        """
        stored_value = self.value[i,
                                  j]                      #Récupérer les résultats stockés dans la liste
        if stored_value is not None:
            return stored_value.get()                      #Si oui, retournez-le

        data = self.check_process(i, j, args)             #Appelez le processus et obtenez le résultat

        container = Container()                             #Préparez un conteneur pour stocker les résultats
        container.set(data)                               #Stocker le résultat dans un conteneur
        #Enregistrez le conteneur (je ne l'enregistre pas directement car je souhaite également n'en enregistrer aucun)
        self.value[i, j] = container
        return data


if __name__ == '__main__':
    class Test(ProcessWithMemory):
        def __init__(self):
            super().__init__(self.func1)

        def func1(self, i, j, message):
            text = "[{}][{}]({})".format(i,j,message)
            if i == 0:
                return text

            retValue = self.process(i - 1, j, text)
            return retValue

if __name__ == '__main__':
    test_terget = Test()
    ret_value = test_terget.func1(3, 2, "message1")
    print(ret_value)

    ret_value = test_terget.func1(3, 2, "message2")
    print(ret_value)

    ret_value = test_terget.func1(3, 1, "message3")
    print(ret_value)

Combinaison du nombre de nombres donnés par chacun

Comme expliqué au début, en comptant les nombres donnés par tous les participants, le schéma du nombre de personnes ayant donné le même nombre est Décomposition additive. Ce sera keirinkan / sansu / WebHelp / 01 / page1_14.html). Puisque P (n, k) requis pour calculer la valeur attendue est (le nombre de combinaisons de nombres qui forment le modèle) / (le nombre de combinaisons de tous les nombres), Vous devez savoir quel est le motif, combien il y a de motifs et le nombre de toutes les combinaisons de nombres. Comme déjà expliqué, le nombre de toutes les combinaisons de nombres est connu pour être $ N ^ p $ lorsque p personnes sont en concurrence avec N nombres. Découvrez quels sont les modèles restants et combien il y en a.

Dans cette section, nous identifierons tous les modèles.

Lorsque 5 est agrégé

1. ５
2. ４＋１
3. ３＋２
4. ３＋１＋１
5. ２＋２＋１
6. ２＋１＋１＋１
   Peut être démonté en.

Cela peut être considéré comme le processus de soustraction de m de 5 et d'agrégation supplémentaire du reste. Aussi, quand N = 3, c'est trop pour se décomposer en quatre, donc dans ce cas 2 + 1 + 1 + 1 de 6) n'est pas nécessaire, et on peut dire que 1) à 5) sont suffisants.

Vous trouverez ci-dessous une classe de DecomposingAddends qui peuvent être ajoutés et décomposés pour identifier des combinaisons de nombres.

DecomposingAddends.py

# ------------------------------------------------------------------------------------------------------------
#
#Décomposition additive
#   N = i0+i1+i2...Trouvez une combinaison qui devient
#
# ------------------------------------------------------------------------------------------------------------
#
#
from ProcessWithMemory import ProcessWithMemory


class DecomposingAddends(ProcessWithMemory):
    def __init__(self):
        """
Décomposition additive: le processus étant récursif, utilisez ProcessWithMemory pour renvoyer le résultat s'il a déjà été calculé.
        """
        super().__init__(self.decomposing)

    def decomposing(self, p, n, dummy):
        """
Décomposition additive
        Parameters
        ----------
        p :Nombre de minutes à ajouter
        n :Nombre maximum de divisions
        dummy :Argument factice pour l'utilisation de ProcessWithMemory (inutilisé))

        Returns
        -------
Liste des résultats agrégés
        """
        if n == 0 and p > 0:            #Aucun lorsque la longueur dépasse n mais il y a un repos
            return None
        if p == 0:                      #Démonté jusqu'au bout
            return [[]]
        elif p == 1:                    #Le reste est 1
            return [[1]]
        else:
            ret_list = [[p]]  #La première liste est p elle-même
            for i in range(p - 1, 0, -1):  # p-1 ..Boucle à 1
                remain = p - i          #Nombre restant
                lower_list = self.process(remain, n - 1, 0)
                #Additionnez davantage avec le nombre restant
                if lower_list is None:  #Le résultat dépasse le nombre maximum de divisions
                    continue            #Ignorer ce résultat
                #Faites une liste avec le nombre restant
                for low in lower_list:  #Une liste des numéros restants
                    if low[0] <= i:     #Les motifs plus grands que moi sont dupliqués et supprimés
                        l1 = [i]        #Sinon, i est au début et le résultat de la décomposition d'addition par les nombres restants est ajouté à la fin.
                        l1.extend(low)
                        ret_list.append(l1)
                        #Inscrivez-vous dans la liste des résultats
            return ret_list


if __name__ == '__main__':

    p = 1
    n = 3
    obj = DecomposingAddends()
    ret = obj.decomposing(p, n, 0)
    print("p={} n={} list={}".format(p, n, ret))

    p = 2
    n = 3
    ret = obj.decomposing(p, n, 0)
    print("p={} n={} list={}".format(p, n, ret))
    p = 3
    n = 3
    ret = obj.decomposing(p, n, 0)
    print("p={} n={} list={}".format(p, n, ret))

    p = 4
    n = 3
    ret = obj.decomposing(p, n, 0)
    print("p={} n={} list={}".format(p, n, ret))

    p = 4
    n = 4
    ret = obj.decomposing(p, n, 0)
    print("p={} n={} list={}".format(p, n, ret))

    p = 5
    n = 3
    ret = obj.decomposing(p, n, 0)
    print("p={} n={} list={}".format(p, n, ret))

    p = 6
    n = 6
    ret = obj.decomposing(p, n, 0)
    print("p={} n={} list={}".format(p, n, ret))

    p = 7
    n = 3
    ret = obj.decomposing(p, n, 0)
    print("p={} n={} list={}".format(p, n, ret))

Comptez le nombre de gagnants

Dans N-ken, le gagnant est la personne qui donne le plus petit nombre, alors trouvez la valeur minimale et la somme de ces valeurs dans la liste obtenue ci-dessus. Au-dessus de p = 7 n = 3 liste = [[7], [6, 1], [5, 2], [5, 1, 1], [4, 3], [4, 2, 1], [ Dans le cas de 3, 3, 1], [3, 2, 2]] [7] ・ ・ ・ ・ ・ Les 7 personnes [6, 1] ・ ・ ・ Une seule personne est différente, donc une personne [5, 2] ・ ・ ・ Deux personnes parce qu'elles ont donné des résultats différents [5, 1, 1] ・ ・ Deux personnes en ont donné des différentes [4, 3] ・ ・ ・ 3 personnes parce qu'elles ont donné des résultats différents [4, 2, 1] ・ ・ L'un des trois types est le plus petit, donc un [3, 3, 1] ・ ・ L'un des trois types est le plus petit, donc un [3, 2, 2] ・ ・ Des trois types, deux sont deux, donc quatre. Sera.

Ceci est calculé en traçant à partir du dos de la liste et en ajoutant jusqu'à ce qu'une valeur supérieure à la dernière valeur soit obtenue.

count_numbers.py

# ------------------------------------------------------------------------------------------------------------
#
#Comptez le nombre de personnes qui ont publié le plus petit nombre de la liste
#
# ------------------------------------------------------------------------------------------------------------
#
#


def count_numbers(terget_list):
    """
Trouvez la somme des plus petits nombres de la liste
    Parameters
    ----------
    terget_list :Liste des cibles

    Returns
    -------
Valeur totale du plus petit nombre
    """
    check_num = terget_list[-1]
    num_of_check_num = terget_list.count(terget_list[-1])
    return num_of_check_num * check_num


if __name__ == '__main__':
    list = [[1]]
    for l in list:
        print("ret={} list={}".format(count_numbers(l), l))
    list = [[2], [1, 1]]
    for l in list:
        print("ret={} list={}".format(count_numbers(l), l))
    list = [[3], [2, 1], [1, 1, 1]]
    for l in list:
        print("ret={} list={}".format(count_numbers(l), l))
    list = [[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
    for l in list:
        print("ret={} list={}".format(count_numbers(l), l))
    list = [
        [5], [
            4, 1], [
            3, 2], [
                3, 1, 1], [
                    2, 2, 1], [
                        2, 1, 1, 1], [
                            1, 1, 1, 1, 1]]
    for l in list:
        print("ret={} list={}".format(count_numbers(l), l))
    list = [
        [6], [
            5, 1], [
            4, 2], [
                4, 1, 1], [
                    3, 3], [
                        3, 2, 1], [
                            3, 1, 1, 1], [
                                2, 2, 2], [
                                    2, 2, 1, 1], [
                                        2, 1, 1, 1, 1], [
                                            1, 1, 1, 1, 1, 1]]
    for l in list:
        print("ret={} list={}".format(count_numbers(l), l))
    list = [
        [7], [
            6, 1], [
            5, 2], [
                5, 1, 1], [
                    4, 3], [
                        4, 2, 1], [
                            4, 1, 1, 1], [
                                3, 3, 1], [
                                    3, 2, 2], [
                                        3, 2, 1, 1], [
                                            3, 1, 1, 1, 1], [
                                                2, 2, 2, 1], [
                                                    2, 2, 1, 1, 1], [
                                                        2, 1, 1, 1, 1, 1], [
                                                            1, 1, 1, 1, 1, 1, 1]]
    for l in list:
        print("ret={} list={}".format(count_numbers(l), l))

Découvrez combien il existe de combinaisons de nombres

À partir de ce qui précède, il est maintenant possible de trouver le modèle de combinaison de nombres lorsque vous jouez avec p personnes et le nombre de gagnants. Comptez le nombre de motifs que la combinaison de nombres obtenue jusqu'à présent est en fait une combinaison de nombres de 0 à (n-1).

Par exemple, si p = 2 personnes, n = 3 et le résultat de la victoire ou de la défaite est [1,1]. Le nombre donné est 0,2, donc Si vous énumérez les modèles où le joueur est respectivement A et B et le résultat de la victoire ou de la défaite est [1,1]

Ce sera 6 modèles de

C'est quand p = 5 personnes, n = 3, et le résultat de la victoire ou de la défaite est [4,1]. Le nombre donné est 0,2, donc

Et, bien que cela continue, il y a 30 façons de le faire.

A partir de maintenant, on calcule qu'il y a 6 voies pour p = 2 personnes, n = 3 et [1,1], et 30 voies pour p = 5 personnes, n = 3 et [4,1]. Me sera demandé.

Si p = 5, n = 3 et [4,1], cela signifie que 4 personnes ont donné le même numéro et qu'une seule personne a donné un numéro différent. Sur les 5 personnes, que 4 personnes ont donné, le nombre est une combinaison qui extrait 4 personnes de 5 personnes. $ _ {5} C_ {4} = 5 $. Celui qui a donné le numéro restant est l'autre personne, il y a donc cinq façons au total. D'autre part, compte tenu du modèle dont le numéro a été donné par 4 personnes et quel numéro a été donné par 1 personne, Puisque N = 3, on peut dire qu'il s'agit d'une séquence dans laquelle deux des trois types de nombres sont retirés et arrangés.

Cela peut donc être représenté par $ _ {3} P_ {2} = 6 $.

Donc,

_{5}C_{4} ☓ _{3}P_{2} = 30

Sera.

Lorsque p = 5 personnes, n = 3 et [3,1,1] La combinaison de trois personnes qui donnent le même nombre est $ _ {5} C_ {3} $. Le reste a donné des nombres différents pour chaque personne, mais la combinaison que le deuxième nombre peut prendre est Trois sur cinq ont déjà été sortis et deux sont restés, et l'un d'entre eux sera décidé, donc $ _ {2} C_ {1} = 2 $. Le reste est décidé automatiquement, donc $ _ {5} C_ {3} ☓ _ {2} C_ {1} = 20 $ C'est vrai.

Quant au nombre donné, si [3,1,1] est [a0, a1, a2], Puisque a0, a1 et a2 sont le nombre de séquences qui peuvent être prises, cela semble être $ _ {3} P_ {3} = 6 $ (je le pensais), Vous finirez par compter a1 et a2, qui sont un chacun.

Dans la combinaison de, A, B, C, D, E, F 5 personnes

Si vous pensez aux deux modèles de

Puis

Ce sera

Même à ce moment-là

Aura le même résultat que.

Par conséquent, il est nécessaire d'éliminer ce cas en double.

Pour considérer comment gérer cette duplication, prenons le cas de P = 6, N = 4. Dans ce cas, il existe un modèle de [a0, a1, a2, a3] = [2,2,1,1] dans lequel quatre nombres sont émis.

Dans ce modèle, la combinaison de modèles dans laquelle 6 personnes donnent chaque nombre de a0, a1, a2, a3 $ _ {6} C_ {2} ☓ _ {4} C_ {2} ☓ _ {2} C_ {1} = 180 $ C'est vrai.

Aussi, Pour qui a émis les numéros pour a0, a1, a2 et a3, Parce que c'est une séquence qui attribue les nombres 0..3 à a0, a1, a2, a3 $ _ {4} P_ {4} = 24 $ C'est vrai.

Cependant, lorsque «la personne (A, B) émet [0] et la personne (C, D) émet [1]» et «la personne (C, D) émet [1]» (A) , B) personne délivrée [0] "est la même et en double La combinaison de x et y affectée à a0 et a1 est la même que la combinaison de y et x affectée à a0 et a1, c'est-à-dire que $ _ {2} P_ {2} $ est dupliqué. Puisque a2 et a3 sont identiques, la combinaison des nombres attribués à [a0, a1, a2, a3] est $ \ frac {_ {4} P_ {4}} {_ {2} P_ {2} ☓ _ {2 Il existe 6 façons de} P_ {2}} $.

Par conséquent, dans le cas de [2,2,1,1], la combinaison de tous les nombres est $ \ frac {_ {6} C_ {2} ☓ _ {4} C_ {2} ☓ _ {2} C_ {1 } ☓ _ {4} P_ {4}} {_ {2} P_ {2} ☓ _ {2} P_ {2}} = 1080 $ C'est vrai.

Dans le cas de [3,1,1,1], a1, a2 et a3 valent tous 1, ce qui est un double. Dans ce modèle, la combinaison de modèles dans laquelle 6 personnes donnent chaque nombre de a0, a1, a2, a3 $ _ {6} C_ {3} ☓ _ {3} C_ {1} ☓ _ {2} C_ {1} = 120 $ Pour qui a émis les numéros pour a0, a1, a2 et a3, $ \ frac {_ {4} P_ {4}} {_ {3} p_ {1}} = 4 $ $ \ Frac {_ {6} C_ {3} ☓ _ {3} C_ {1} ☓ _ {2} C_ {1} ☓ _ {4} P_ {4}} {_ {3} P_ {1}} = 480 $ C'est vrai.

Sur la base de la considération ci-dessus, nous avons créé un code pour trouver le nombre de modèles lorsque le nombre de chaque nombre est [a0, a1, a2, a3] lorsqu'une p personne sort de N nombres. Je vais.

Combinations.py

# ------------------------------------------------------------------------------------------------------------
#
#Le nombre d'apparitions de chaque numéro[a0,a1..am]Trouvez le nombre total de combinaisons de nombres lorsque
#
# ------------------------------------------------------------------------------------------------------------
#
from scipy.special import perm, comb          #Pour le calcul des combinaisons ordinales


class Combinations:

    def __init__(self, n, terget_list):
        self.n = n
        self.terget_list = terget_list

    def redundancy(self):
        """
Calculer le nombre à supprimer en raison de la duplication
        Parameters
        ----------
        Returns
        -------
Nombre à diviser en raison de la duplication
        """
        current_value = 0                       #Numéro pour vérifier les doublons
        counter = 0                             #Le nombre de ce nombre
        result = 1                              #résultat
        for i in self.terget_list:
            if current_value != i:
                p = perm(counter, counter)      # cPc :Nombre de motifs en double
                result = result * p             #Multiplier par le nombre de modèles précédents en double
                counter = 1                     #Parce qu'il y en a un
                current_value = i               #Numéro suivant pour vérifier les doublons
            else:
                counter += 1                    #Le même numéro continue

        p = perm(counter, counter)              #Dernière opération sur la dernière valeur
        result = result * p
        return result

    def player_combinations(self):
        """
Trouvez la séquence de modèles que les participants peuvent suivre
        Parameters
        ----------
        n :Gamme de valeurs
        terget_list :Liste à vérifier (modèle de combien de chaque numéro a été émis)

        Returns
        -------
Nombre de modèles que les participants peuvent suivre
        """
        length = len(self.terget_list)               #Combien de types de nombres ont été donnés
        permut = perm(self.n, length)                #Ordre des numéros émis parmi tous les numéros
        result = permut / self.redundancy()          #Supprimer les doublons
        return result

    def number_combinations(self):
        """
Obtenez le nombre de combinaisons de nombres
        Returns
        -------
Nombre de combinaisons de nombres
        """
        remain = sum(self.terget_list)                      #Demandez le nombre de participants
        result = 1                                          #Valeur initiale du résultat
        for i in self.terget_list:
            #Combinaison quand je donne le même numéro
            combin = comb(remain, i)
            result = result * combin                        #Pouvoir total
            remain = remain - i                             #Nombre de personnes restant

        return result

    def get(self):
        numbers = self.number_combinations()
        players = self.player_combinations()
        return numbers * players


if __name__ == '__main__':

    test_data = [1, 1]
    n = 2
    obj = Combinations(n, test_data)
    print("Combinations={} list={}".format(obj.get(), test_data))

    test_data = [1, 2]
    n = 2
    obj = Combinations(n, test_data)
    print("Combinations={} list={}".format(obj.get(), test_data))

    test_data = [2, 2, 2]
    n = 4
    obj = Combinations(n, test_data)
    print("Combinations={} list={}".format(obj.get(), test_data))

    test_data = [3, 1, 1, 1]
    n = 4
    obj = Combinations(n, test_data)
    print("Combinations={} list={}".format(obj.get(), test_data))

    test_data = [2, 2, 1, 1]
    n = 4
    obj = Combinations(n, test_data)
    print("Combinations={} list={}".format(obj.get(), test_data))

Comptez le nombre de motifs pour chaque nombre de gagnants

Formule pour trouver la valeur attendue \displaystyle E_{n} = \frac{1 + \sum_{k=1}^{n-1} P(n,k)E_{k}}{(1- P(n,n))}
Ce qu'il faut, c'est "la probabilité du nombre de personnes qu'il reste à gagner" et "la valeur attendue du nombre de personnes qui ont gagné", mais puisque "la valeur attendue du nombre de personnes qui ont gagné" est calculée récursivement. Calculez la «probabilité de combien de personnes il reste à gagner».

"Probabilité de combien de personnes il reste à gagner" est (combien de modèles y a-t-il pour chaque personne restante) / (tous les modèles) Comptez le nombre total de modèles pour chaque gagnant restant.

Le processus de comptage du nombre de combinaisons possibles de nombres pour chaque nombre restant de gagnants est le suivant.

1. Listez les combinaisons de nombres données par chacun
2. Découvrez combien de modèles de nombres sont répertoriés
3. Découvrez combien de personnes il reste à gagner dans les modèles de nombres énumérés
4. Calculez le nombre total de modèles de nombres pour chaque nombre restant de gagnants Si vous pouvez le faire jusqu'à présent, vous pouvez trouver la probabilité en divisant par le nombre total de tous les modèles, afin que vous puissiez obtenir la probabilité pour chaque nombre restant de gagnants.

Probability.py

# ------------------------------------------------------------------------------------------------------------
#
#Trouvez la probabilité pour chaque nombre restant de gagnants
#
# ------------------------------------------------------------------------------------------------------------
#
from ExpandList import ExpandList2D
from DecomposingAddends import DecomposingAddends
from Combinations import Combinations
from count_numbers import count_numbers


class Probability:
    result_list = ExpandList2D()

    def __init__(self, p, n):
        """
Trouvez la probabilité pour chaque nombre restant de gagnants
        Parameters
        ----------
        p :Le nombre de participants
        n :Nombre de numéros donnés par les participants
        """
        self.p = p
        self.n = n

    def sum_patterns_by_winner(self):
        """
Agréger le nombre de modèles de combinaison pour chaque nombre restant de gagnants
        Returns
        -------
        list[Nombre de gagnants] :Nombre de motifs de combinaison
        """
        #Faites une liste des résultats gagnés / perdus
        decomp_list = DecomposingAddends().decomposing(self.p, self.n, 0)

        #Préparez une liste pour entrer le nombre de modèles pour le nombre de participants(1 origine)
        self.patterns = [0] * (self.p + 1)
        #À partir de la liste des résultats, par le nombre de gagnants restants
        for l in decomp_list:
            patterns = Combinations(self.n, l).get()  #À partir du modèle de résultat, obtenez le nombre de modèles dans lesquels il se produit
            winners = count_numbers(l)                  #Obtenez le nombre de personnes qui restent pour gagner
            self.patterns[winners] += patterns

        return self.patterns

    def culc(self):
        result = Probability.result_list[self.p, self.n]
        if result is not None:                              #Si vous avez déjà calculé, utilisez cette valeur
            return result

        patterns = self.sum_patterns_by_winner()
        total = self.n ** self.p
        self.probability = [0.0] * (self.p)             #Préparez une liste pour saisir la probabilité du nombre de participants
        for i in range(1, self.p):
            self.probability[i] = patterns[i] / total    #Trouvez la probabilité

        self.probability[0] = patterns[self.p] / total  #Le dernier (tout de même)Magasins en 0e

        Probability.result_list[self.p, self.n] = self.probability
        #Enregistrer le résultat du calcul
        return self.probability


if __name__ == '__main__':
    p = 3
    n = 3
    pList = Probability(p, n).culc()
    print("p={} n={} result={}".format(p, n, pList))

    p = 4
    n = 2
    pList = Probability(p, n).culc()
    print("p={} n={} result={}".format(p, n, pList))

    p = 4
    n = 3
    pList = Probability(p, n).culc()
    print("p={} n={} result={}".format(p, n, pList))

    p = 5
    n = 3
    pList = Probability(p, n).culc()
    print("p={} n={} result={}".format(p, n, pList))

    p = 6
    n = 4
    pList = Probability(p, n).culc()
    print("p={} n={} result={}".format(p, n, pList))

    p = 5
    n = 3
    pList = Probability(p, n).culc()
    print("p={} n={} result={}".format(p, n, pList))

Maintenant que nous connaissons la probabilité de chaque nombre restant de gagnants, nous allons enfin trouver la valeur attendue. Comme déjà expliqué, la valeur attendue est calculée par la formule suivante. \displaystyle E_{n} = \frac{1 + \sum_{k=1}^{n-1} P(n,k)E_{k}}{(1- P(n,n))}

ExpectedValue.py

# ------------------------------------------------------------------------------------------------------------
#
#Trouvez la valeur attendue
#
# ------------------------------------------------------------------------------------------------------------
#
#
from Probability import Probability
from ProcessWithMemory import ProcessWithMemory


class ExpectedValue (ProcessWithMemory):
    def __init__(self):
        super().__init__(self.calculation)

    def calculation(self, p, n, dummy):
        if p <= 1:                                 #Terminer s'il y a moins d'un gagnant
            return 0.0
        elif p == 2:                                #Quand il y a deux personnes, il n'y a pas de correspondance, donc 1 de Janken.Adoptez 5
            return 1.5
        else:
            probability = Probability(p, n).calculation()        #Liste des chances de gagner des personnes
            result = 1
            for i in range(1, p):
                probability_i = probability[i]         #Probabilité que je reste des gagnants
                expected_value = self.process(i, n, dummy)
                expected_value = (probability_i * expected_value)
                result = result + expected_value

            result = result / (1 - probability[0])       # (1-Probabilité que tout le monde survivra)Diviser par

        return result


if __name__ == '__main__':
    obj = ExpectedValue()

    for p in range(3, 6):
        for n in range(2, p + 1):
            probability = obj.calculation(p, n, 0)
            print("p={} n={} result={}".format(p, n, probability))

Résumé

Enfin, formatez-le dans un tableau et trouvez le n avec la valeur attendue la plus basse pour chaque p.

NKen.py

# ------------------------------------------------------------------------------------------------------------
#
#N poing: 0 joueurs..(n-1)Un jeu dans lequel le gagnant est la personne qui donne le nombre jusqu'à n et donne le nombre avec le moins de personnes.
#Ici, dans N poing, quand il y a p personnes, on examine combien de fois n est optimal.
#
# ------------------------------------------------------------------------------------------------------------
#
from ExpectedValue import ExpectedValue

expected_value_obj = ExpectedValue()            #Objet pour calculer la valeur attendue

maxP = 30
text = "|p\\n|"
for n in range(2, maxP):
    text = text + "{:2d}|".format(n)             #Étiquette de colonne
print(text)

text = "|-|"
for n in range(2, maxP):
    text = text + "----|".format(n)             #Ligne horizontale de colonne
print(text)

for p in range(3, maxP):
    text = ""
    min_expected_value = float('inf')
    min_expected_value_n = 0
    for n in range(2, p + 1):
        expected_value = expected_value_obj.calculation(p, n, 0)
        text = text + "{:1.3f}|".format(expected_value)
        if expected_value < min_expected_value:
            min_expected_value = expected_value
            min_expected_value_n = n

    text = "p={:2d} n={:2d}[{:1.3f}]|".format(
        p, min_expected_value_n, min_expected_value) + text
    print(text)