[PYTHON] Die Geschichte, das optimale n in N Faust zu finden

Was ist N Faust

Wenn es viele Leute gibt, ist es schwer zu gewinnen oder zu verlieren, selbst wenn man es spielt, und ich denke, jeder hat die Erfahrung, lange zu dauern. Wenn Sie dies mit "Janken Expected Value" umgehen, werden Sie viele Artikel finden, daher werde ich die Erklärung weglassen, aber Auf der Seite Durchschnittlich oft, um eine Person mit Janken zu entscheiden wird ein Gewinner für 2 bis 50 Personen ermittelt. Die durchschnittliche Häufigkeit bis wird aufgeführt. Bei 8 Personen waren es bereits 12,1-mal mehr als 10-mal.

Auf diese Weise ist es schwierig, sich zu messen, wenn es eine große Anzahl von Menschen gibt, aber um dies zu lösen, werden wir N Faust betrachten.

N-Ken ist ein Spiel, bei dem die Teilnehmer freiwillig eine der N Zahlen von 0 bis (N-1) austauschen und die Person, die die kleinste Zahl gibt, der Gewinner ist. Wenn beispielsweise 5 Teilnehmer anwesend sind, wird eine der drei Zahlen bis zu 0,2 angegeben, und als Ergebnis werden 2,0,2,1,0 und 1 angegeben, wenn die Zahlen angegeben werden. Die Anzahl der Personen ist am geringsten, daher ist die Person, die 1 gibt, der Gewinner. Mit dieser Regel können Sie als Zwei-Personen niemals gewinnen oder verlieren. Daher beträgt die Mindestanzahl von Personen drei.

Nach meiner bisherigen Forschung scheint es, wenn N 3 ist, etwas zu geben, das "Gamer Janken" genannt wird. Wenn N 5 ist, scheint es etwas zu geben, das "Ippatsu Janken" genannt wird. Zuerst habe ich dieses Spiel auch "Mehrere Fäuste" genannt, aber es scheint, dass es in der Meiji-Ära nach einer anderen Regel existierte. Als nächstes nannte ich es "Numerical Fist", was in China zu existieren scheint.

In diesem Artikel wollen wir den optimalen N-Wert für diese N Faust berechnen, wenn p Teilnehmer anwesend sind (dh ein Gewinner wird durch die Mindestanzahl von Malen bestimmt). Wie bereits erwähnt, gibt es keinen Gewinn oder Verlust, wenn am Ende zwei Personen übrig bleiben. Daher übernehmen wir den erwarteten Wert von 1,5 für Janken.

Kombination der Anzahl der ausgegebenen Nummern

Wenn zum Beispiel 5 Teilnehmer vorhanden sind und N 3 ist, ist die Hand, die jeder Teilnehmer nimmt Es wird $ 3 ^ 5 $ sein. Dies geht aus der Tatsache hervor, dass die Folge von ternären Zahlen von 00000 bis 22222 100.000 ternäre Zahlen oder $ 3 ^ 5 $ beträgt. Das heißt, wenn p Personen mit N Zahlen konkurrieren, ist die von jedem Teilnehmer angegebene Zahlenfolge N^p
Es wird auf der Straße sein.

Wenn Sie die Zahlen 0, 1 und 2 zählen, wie viele Personen sie löschen, Die Kombination ist dieselbe wie die Kombination von Zahlen, die durch Multiplizieren von p erhalten wird. Wir werden dies später als "Ergebnismuster" bezeichnen.

Zum Beispiel im obigen Beispiel

1. 5 Personen geben die gleiche Nummer
2. 4 Personen geben die gleiche Nummer, 1 Person gibt eine andere Nummer
3. 3 Personen geben die gleiche Nummer, 2 Personen geben unterschiedliche Nummern
4. 3 Personen geben die gleiche Nummer, 2 Personen geben unterschiedliche Nummern
5. Zwei Personen geben die gleiche Nummer an, zwei Personen geben unterschiedliche Nummern an und eine Person gibt die verbleibende Nummer an

Es gibt 5 Muster von, aber dies entspricht dem Muster, das 5 aus den aggregierten Zahlen in 3 teilt.

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

Der erwartete Wert wird bestimmt durch "Eintrittswahrscheinlichkeit x Wert, wenn er auftritt". Durch Ermitteln der Auftrittswahrscheinlichkeit dieses Ergebnismusters kann der erwartete Wert ermittelt werden. Das Ermitteln der Wahrscheinlichkeit des Auftretens eines Ergebnismusters bedeutet mit anderen Worten, wie viele Muster sich in diesem Muster aus allen $ N ^ p $ -Zeiten befinden.

Erwarteter Wert, wenn das Spiel wiederholt wird

In diesem Spiel wird nicht immer ein Gewinner gleichzeitig ermittelt. Wenn es im obigen Beispiel eine Person gibt, die 1 gegeben hat, und eine Person, die 2 gegeben hat, sind sowohl die Person, die 1 gegeben hat, als auch die Person, die 2 gegeben hat, die Gewinner, und die beiden spielen das Spiel erneut. .. Bei zwei Personen gibt es jedoch keinen Sieg oder keine Niederlage, sodass die endgültige Entscheidung von Janken getroffen wird. Im obigen Beispiel ist 4) dieser Fall. Auch in 3) gibt es zwei Gewinner, weil die beiden die Zahlen angeben, die weniger gegeben wurden.

Wenn zum Beispiel 7 Teilnehmer mit N = 3 konkurrieren 7=3+2+2
In der Kombination von gibt es 4 Gewinner.

Diese Gewinner spielen das Spiel erneut und schränken die Gewinner ein.

Den erwarteten Wert der Anzahl der Spiele, die durch Extrahieren dieses Gewinners wiederholt werden sollen, finden Sie im Artikel Berechnen Sie die durchschnittliche Anzahl von Malen bis zum Ende von Janken. Es gibt eine Erklärung E_n = \sum_{k=1}^{n} P(n,k)(E_{k}+1)
Wird sein.

$ E_n $ ist der erwartete Wert, wenn die Anzahl der Personen n ist, und P (n, k) ist die Wahrscheinlichkeit, wenn k Personen gewinnen, wenn die Anzahl der Personen n ist. Diese Formel kann in $ E_n = 1 + \ sum_ {k = 1} ^ {n} P (n, k) E_ {k} $ umgewandelt werden.

Auch wenn Sie den mathematischen Beweis dieser Formel nicht kennen, wenn es diese Formel ist "Der erwartete Wert $ E_n $ ist ($ E_n = ), versuchen Sie es einmal (1 +), und wenn die Anzahl der Gewinner k (P (n, k)) ist und Sie mehr gewinnen. Multiplizieren Sie den erwarteten Wert von ( E_ {k}) $ und addieren Sie die Fälle aller verbleibenden Personen ($ \ sum_ {k = 1} ^ {n} $) ", so dass ich denke, dass es leicht zu verstehen ist. Ich werde.

So wie es ist, befindet sich der Term von k = n auf der rechten Seite und $ E_ {n} $ existiert sowohl auf der linken als auch auf der rechten Seite. Wenn Sie die Logik so erstellen, wie sie ist, ist dies ein unendlicher rekursiver Prozess. Dies weiter

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

Transformiert und

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))}

Auf diese Weise können Sie den erwarteten Wert ermitteln.

Rekursive Verarbeitung

Von nun an werden wir einen Prozess erstellen, um den erwarteten Wert zu ermitteln. Während des Prozesses wird die rekursive Verarbeitung jedoch von nun an viele Male angezeigt. Die Berechnung des unteren Werts wird mehrmals vom oberen Wert aufgerufen, es ist jedoch eine Verschwendung von Verarbeitungsgeschwindigkeit, genau dieselbe Berechnung durchzuführen. Bereiten Sie daher nach der Berechnung eine vor, die das Berechnungsergebnis sofort beim nächsten Mal zurückgibt. Ich werde das machen.

Um diesen Prozess zu implementieren, erstellen Sie außerdem eine Liste, die auch dann keine Ausnahme macht, wenn Sie außerhalb des Bereichs der Liste zugreifen, in der der Wert festgelegt ist.

ExpandList.py

# ------------------------------------------------------------------------------------------------------------
#
#Wird beim Zugriff außerhalb der Liste automatisch erweitert
#
#Herr Shiracamus erklärte, wie man durch Erben der Liste realisiert.
#Vielen Dank.
#Ich habe es entsprechend umgeschrieben.
#
# ------------------------------------------------------------------------------------------------------------
#


class ExpandList(list):
    def __setitem__(self, i, value):
        """
Stellen Sie den Wert an der angegebenen Position ein
        Parameters
        ----------
        i :Index
        value :Zu setzender Wert
        """
        if i >= len(self):
            self.extend([None] * (i - len(self) + 1))
        super().__setitem__(i, value)

    def __getitem__(self, i):
        """
Rufen Sie den Wert vom angegebenen Speicherort ab
        Parameters
        ----------
        i :Index

        Returns :
        -------
            (Wenn in Reichweite) :Wert an der angegebenen Position
            (Wenn außerhalb der Reichweite) : None
        """

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


class ExpandList2D(ExpandList):
    def __setitem__(self, pos, value):
        """
Stellen Sie den Wert an der angegebenen Position ein
        Parameters
        ----------
        pos :Index
        value :Zu setzender Wert
        """

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

    def __getitem__(self, pos):
        """
Rufen Sie den Wert vom angegebenen Speicherort ab
        Parameters
        ----------
        pos :Index
        Returns :
        -------
            (Wenn in Reichweite) :Wert an der angegebenen Position
            (Wenn außerhalb der Reichweite) : 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])

Der obige Prozess gibt None zurück, wenn der außerhalb des Bereichs liegende Wert für die eindimensionale Liste und die zweidimensionale Liste gelesen wird, und get (), das den gespeicherten Wert andernfalls zurückgibt. Wenn Sie außerhalb des Bereichs angeben und speichern, wird die Liste erweitert und gespeichert. ~~ Es erbt die Liste nicht und ist kein Iterator, aber es reicht für diesen Zweck, also wird es auf diese Weise implementiert. ~~

~~ Da es um Python geht, gibt es vielleicht schon etwas Nützlicheres, aber ich konnte es nach einer Weile nicht finden, also werde ich es einfach benutzen. ~~ Ich habe einen Kommentar von @shiracamus erhalten und ihn so geändert, dass er von der Liste erbt.

Erstellen Sie als Nächstes eine Klasse, die den gespeicherten Wert zurückgibt, wenn er bereits berechnet wurde, und die Methode rekursiv aufruft, wenn er noch nicht berechnet wurde.

ProcessWithMemory.py

# ------------------------------------------------------------------------------------------------------------
#
#Die einmal berechnete Verarbeitung liefert das Ergebnis ohne Berechnung
#
# ------------------------------------------------------------------------------------------------------------
#
from ExpandList import ExpandList2D


class Container:
    def __init__(self):
        """
Container zum Speichern von Werten
        """
        self.value = None

    def get(self):
        """
Holen Sie sich den gespeicherten Wert
        Returns
        -------
Gespeicherter Wert
        """
        return self.value

    def set(self, data):
        """
Wert speichern
        Parameters
        ----------
        data :Wert zu speichern
        """
        self.value = data


class ProcessWithMemory:
    def __init__(self, function):
        """
Eine Klasse, die den gespeicherten Wert zurückgibt, falls vorhanden, und den Prozess anderweitig aufruft
        """
        self.value = ExpandList2D()
        self.check_process = function

    def process(self, i, j, *args):
        """
Überprüft, ob es bereits berechnet wurde, gibt den Wert zurück, wenn dies der Fall ist, und ruft die registrierte Methode auf, wenn nicht
        Parameters
        ----------
        i :Index 1. Dimension
        j :Index 2. Dimension
        kwargs :Argument variabler Länge

        Returns
        -------
Ergebniswert
        """
        stored_value = self.value[i,
                                  j]                      #Rufen Sie die in der Liste gespeicherten Ergebnisse ab
        if stored_value is not None:
            return stored_value.get()                      #Wenn ja, geben Sie es zurück

        data = self.check_process(i, j, args)             #Prozess aufrufen und Ergebnis erhalten

        container = Container()                             #Bereiten Sie einen Container vor, um die Ergebnisse zu speichern
        container.set(data)                               #Speichern Sie das Ergebnis in einem Behälter
        #Speichern Sie den Container (ich speichere ihn nicht direkt, weil ich auch None speichern möchte)
        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)

Kombination der Anzahl der von allen angegebenen Zahlen

Wie eingangs erläutert, ist bei der Zählung der von allen Teilnehmern angegebenen Zahlen das Muster, wie viele Personen dieselbe Zahl angegeben haben, Additive Zerlegung. Es wird keirinkan / sansu / WebHelp / 01 / page1_14.html sein. Da P (n, k), das zur Berechnung des erwarteten Werts erforderlich ist, (die Anzahl der Zahlenkombinationen, die das Muster bilden) / (die Anzahl der Kombinationen aller Zahlen) ist, Sie müssen herausfinden, was das Muster ist, wie viele Muster es gibt und wie viele Zahlenkombinationen es gibt. Wie bereits erläutert, ist bekannt, dass die Anzahl aller Zahlenkombinationen $ N ^ p $ ist, wenn p Personen mit N Zahlen konkurrieren. Finden Sie heraus, was die verbleibenden Muster sind und wie viele davon es gibt.

In diesem Abschnitt werden alle Muster identifiziert.

Wenn 5 aggregiert ist

1. ５
2. ４＋１
3. ３＋２
4. ３＋１＋１
5. ２＋２＋１
6. ２＋１＋１＋１
   Kann zerlegt werden in.

Dies kann als der Prozess des Subtrahierens von m von 5 und des weiteren Aggregierens des Restes angesehen werden. Auch wenn N = 3 ist, ist es zu viel, um in vier zu zerfallen, so dass in diesem Fall 2 + 1 + 1 + 1 von 6) nicht notwendig ist, und man kann sagen, dass 1) bis 5) ausreichend sind.

Unten finden Sie eine Klasse von DecomposingAddends, die hinzugefügt und zerlegt werden können, um Kombinationen von Zahlen zu identifizieren.

DecomposingAddends.py

# ------------------------------------------------------------------------------------------------------------
#
#Additive Zersetzung
#   N = i0+i1+i2...Ich suche eine Kombination, die wird
#
# ------------------------------------------------------------------------------------------------------------
#
#
from ProcessWithMemory import ProcessWithMemory


class DecomposingAddends(ProcessWithMemory):
    def __init__(self):
        """
Additive Zerlegung: Da der Prozess rekursiv ist, verwenden Sie ProcessWithMemory, um das Ergebnis zurückzugeben, wenn es bereits berechnet wurde.
        """
        super().__init__(self.decomposing)

    def decomposing(self, p, n, dummy):
        """
Additive Zersetzung
        Parameters
        ----------
        p :Anzahl der hinzuzufügenden Minuten
        n :Maximale Anzahl von Abteilungen
        dummy :Dummy-Argument für die Verwendung von ProcessWithMemory (nicht verwendet))

        Returns
        -------
Liste der Gesamtergebnisse
        """
        if n == 0 and p > 0:            #Keine, wenn die Länge n überschreitet, aber es gibt eine Pause
            return None
        if p == 0:                      #Bis zum Ende zerlegt
            return [[]]
        elif p == 1:                    #Der Rest ist 1
            return [[1]]
        else:
            ret_list = [[p]]  #Die erste Liste ist p selbst
            for i in range(p - 1, 0, -1):  # p-1 ..Schleife zu 1
                remain = p - i          #Verbleibende Nummer
                lower_list = self.process(remain, n - 1, 0)
                #Addieren Sie weiter mit der verbleibenden Anzahl
                if lower_list is None:  #Das Ergebnis überschreitet die maximale Anzahl von Abteilungen
                    continue            #Ignorieren Sie dieses Ergebnis
                #Machen Sie eine Liste mit der restlichen Nummer
                for low in lower_list:  #Eine Liste der verbleibenden Nummern
                    if low[0] <= i:     #Muster, die größer als i sind, werden dupliziert und entfernt
                        l1 = [i]        #Andernfalls steht i am Anfang und das Additionszerlegungsergebnis durch die verbleibenden Zahlen wird am Ende addiert.
                        l1.extend(low)
                        ret_list.append(l1)
                        #Registrieren Sie sich in der Ergebnisliste
            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))

Zählen Sie die Anzahl der Gewinner

In N-Ken ist der Gewinner die Person, die die kleinste Zahl angibt. Suchen Sie also den Mindestwert und die Summe dieser Werte aus der oben erhaltenen Liste. Über p = 7 n = 3 list = [[7], [6, 1], [5, 2], [5, 1, 1], [4, 3], [4, 2, 1], [ Im Fall von 3, 3, 1], [3, 2, 2]] [7] 7 ・ ・ ・ ・ Alle 7 Personen [6, 1] ・ ・ ・ Nur eine Person ist anders, also eine Person [5, 2] people ・ ・ Zwei Personen, weil sie unterschiedliche Ergebnisse lieferten [5, 1, 1] ・ ・ Zwei Personen gaben unterschiedliche [4, 3] people ・ ・ 3 Personen, weil sie unterschiedliche Ergebnisse lieferten [4, 2, 1] ・ ・ Einer der drei Typen ist der kleinste, also einer [3, 3, 1] ・ ・ Einer der drei Typen ist der kleinste, also einer [3, 2, 2] ・ ・ Von den drei Typen sind zwei zwei, also vier. Wird sein.

Dies wird berechnet, indem vom Ende der Liste aus verfolgt und addiert wird, bis ein Wert erhalten wird, der größer als der letzte Wert ist.

count_numbers.py

# ------------------------------------------------------------------------------------------------------------
#
#Zählen Sie die Anzahl der Personen, die die kleinste Anzahl in der Liste ausgegeben haben
#
# ------------------------------------------------------------------------------------------------------------
#
#


def count_numbers(terget_list):
    """
Finden Sie die Summe der kleinsten Zahlen in der Liste
    Parameters
    ----------
    terget_list :Zielliste

    Returns
    -------
Gesamtwert der kleinsten Zahl
    """
    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))

Finden Sie heraus, wie viele Kombinationen von Nummernnummern es gibt

Aus dem Obigen ist es nun möglich, das Kombinationsmuster von Zahlen beim Spielen mit p Personen und die Anzahl der Gewinner zu ermitteln. Zählen Sie, wie viele Muster die bisher erhaltene Zahlenkombination tatsächlich eine Zahlenkombination von 0 bis (n-1) ist.

Wenn zum Beispiel p = 2 Personen ist, ist n = 3 und das Ergebnis eines Sieges oder einer Niederlage ist [1,1]. Die angegebene Zahl ist also 0,2 Wenn Sie die Muster aufzählen, bei denen der Spieler A bzw. B ist und das Ergebnis eines Sieges oder einer Niederlage [1,1] ist.

Es werden 6 Muster von sein

Dies ist, wenn p = 5 Personen, n = 3 und das Ergebnis eines Sieges oder einer Niederlage [4,1] ist. Die angegebene Zahl ist also 0,2

Und obwohl es so weitergeht, gibt es 30 Möglichkeiten.

Von nun an wird berechnet, dass es 6 Möglichkeiten für p = 2 Personen, n = 3 und [1,1] und 30 Möglichkeiten für p = 5 Personen, n = 3 und [4,1] gibt. Ich werde gefragt.

Wenn p = 5, n = 3 und [4,1], bedeutet dies, dass 4 Personen dieselbe Nummer und nur 1 Person eine andere Nummer gaben. Von den 5 Personen, denen 4 Personen die Nummer gaben, ist eine Kombination, die 4 Personen aus 5 Personen extrahiert. $ _ {5} C_ {4} = 5 $. Derjenige, der die verbleibende eine Nummer gegeben hat, ist die andere Person, also gibt es insgesamt fünf Möglichkeiten. In Anbetracht des Musters, welche Nummer von 4 Personen und welche von 1 Person angegeben wurde, Da N = 3 ist, kann gesagt werden, dass es sich um eine Sequenz handelt, in der zwei der drei Arten von Zahlen herausgenommen und angeordnet werden.

Dies kann also durch $ _ {3} P_ {2} = 6 $ dargestellt werden.

Deshalb,

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

Wird sein.

Wenn p = 5 Personen, n = 3 und [3,1,1] Die Kombination von drei Personen, die dieselbe Nummer angeben, ist $ _ {5} C_ {3} $. Der Rest gab unterschiedliche Nummern für jede Person, aber die Kombination, die die zweite Nummer annehmen kann, ist Drei von fünf wurden bereits gelöscht und zwei sind noch übrig, und einer von ihnen wird entschieden, also $ _ {2} C_ {1} = 2 $. Der verbleibende wird also automatisch entschieden $ _ {5} C_ {3} ☓ _ {2} C_ {1} = 20 $ Das stimmt.

Welche Zahl wurde angegeben, wenn [3,1,1] [a0, a1, a2] ist? Da a0, a1 und a2 die Anzahl der Sequenzen sind, die genommen werden können, scheint es $ _ {3} P_ {3} = 6 $ zu sein (ich dachte schon), Am Ende zählen Sie a1 und a2, die jeweils eins sind.

In der Kombination von A, B, C, D, E, F 5 Personen

Wenn Sie über die beiden Muster von nachdenken

Dann

Es wird sein

Schon damals

Wird das gleiche Ergebnis haben wie.

Daher ist es notwendig, diesen doppelten Fall zu beseitigen.

Um zu überlegen, wie mit dieser Duplizierung umgegangen werden soll, nehmen wir den Fall P = 6, N = 4. In diesem Fall gibt es ein Muster von [a0, a1, a2, a3] = [2,2,1,1], in dem vier Zahlen ausgegeben werden.

In diesem Muster die Kombination von Mustern, in denen 6 Personen jede Zahl von a0, a1, a2, a3 geben $ _ {6} C_ {2} ☓ _ {4} C_ {2} ☓ _ {2} C_ {1} = 180 $ Das stimmt.

Ebenfalls, Für diejenigen, die die Zahlen für a0, a1, a2 und a3 ausgegeben haben, Weil es eine Sequenz ist, die a0, a1, a2, a3 die Nummern 0..3 zuweist $ _ {4} P_ {4} = 24 $ Das stimmt.

Wenn jedoch "die Person (A, B) [0] und die Person (C, D) [1] ausgibt" und "die Person (C, D) [1] ausgibt" (A) , B) Person ausgestellt [0] "ist die gleiche und doppelt Die Kombination von x und y, die a0 und a1 zugewiesen ist, ist dieselbe wie die Kombination von y und x, die a0 und a1 zugewiesen ist, dh $ _ {2} P_ {2} $ wird dupliziert. Da a2 und a3 gleich sind, ist die Kombination der [a0, a1, a2, a3] zugewiesenen Zahlen $ \ frac {_ {4} P_ {4}} {_ {2} P_ {2} ☓ _ {2 Es gibt 6 Möglichkeiten für} P_ {2}} $.

Daher ist die Kombination aller Zahlen im Fall von [2,2,1,1] $ \ frac {_ {6} C_ {2} ☓ _ {4} C_ {2} ☓ _ {2} C_ {1 } ☓ _ {4} P_ {4}} {_ {2} P_ {2} ☓ _ {2} P_ {2}} = 1080 $ Das stimmt.

Im Fall von [3,1,1,1] sind a1, a2 und a3 alle 1, was ein Duplikat ist. In diesem Muster die Kombination von Mustern, in denen 6 Personen jede Zahl von a0, a1, a2, a3 geben $ _ {6} C_ {3} {_ {3} C_ {1} ☓ _ {2} C_ {1} = 120 $ Für diejenigen, die die Zahlen für a0, a1, a2 und a3 ausgegeben haben, $ \ 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 $ Das stimmt.

Basierend auf der obigen Überlegung haben wir einen Code erstellt, um die Anzahl der Muster zu ermitteln, wenn die Anzahl jeder Zahl [a0, a1, a2, a3] ist, wenn eine p-Person aus N Zahlen hervorgeht. Ich werde.

Combinations.py

# ------------------------------------------------------------------------------------------------------------
#
#Die Anzahl der Auftritte jeder Nummer[a0,a1..am]Finden Sie die Gesamtzahl der Zahlenkombinationen, wenn
#
# ------------------------------------------------------------------------------------------------------------
#
from scipy.special import perm, comb          #Zur Berechnung von Ordnungskombinationen


class Combinations:

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

    def redundancy(self):
        """
Berechnen Sie die Anzahl, die aufgrund von Duplikaten entfernt werden soll
        Parameters
        ----------
        Returns
        -------
Nummer, die aufgrund von Doppelarbeit geteilt werden soll
        """
        current_value = 0                       #Nummer, um nach Duplikaten zu suchen
        counter = 0                             #Die Nummer dieser Nummer
        result = 1                              #Ergebnis
        for i in self.terget_list:
            if current_value != i:
                p = perm(counter, counter)      # cPc :Anzahl der doppelten Muster
                result = result * p             #Multiplizieren Sie mit der Anzahl der vorherigen doppelten Muster
                counter = 1                     #Weil es einen gibt
                current_value = i               #Nächste Nummer, um nach Duplikaten zu suchen
            else:
                counter += 1                    #Die gleiche Nummer geht weiter

        p = perm(counter, counter)              #Letzte Operation am letzten Wert
        result = result * p
        return result

    def player_combinations(self):
        """
Finden Sie die Reihenfolge der Muster, die die Teilnehmer annehmen können
        Parameters
        ----------
        n :Wertebereich
        terget_list :Zu überprüfende Liste (Muster, wie viele jede Nummer ausgegeben wurde)

        Returns
        -------
Anzahl der Muster, die die Teilnehmer annehmen können
        """
        length = len(self.terget_list)               #Wie viele Arten von Zahlen wurden gegeben
        permut = perm(self.n, length)                #Reihenfolge der aus allen Nummern ausgegebenen Nummern
        result = permut / self.redundancy()          #Duplikate entfernen
        return result

    def number_combinations(self):
        """
Ermitteln Sie die Anzahl der Zahlenkombinationen
        Returns
        -------
Anzahl der Zahlenkombinationen
        """
        remain = sum(self.terget_list)                      #Fragen Sie nach der Anzahl der Teilnehmer
        result = 1                                          #Anfangswert des Ergebnisses
        for i in self.terget_list:
            #Kombination, wenn ich Leute die gleiche Nummer geben
            combin = comb(remain, i)
            result = result * combin                        #Totale Kraft
            remain = remain - i                             #Verbleibende Anzahl von Personen

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

Zählen Sie die Anzahl der Muster für jede Anzahl der Gewinner

Formel, um den erwarteten Wert zu finden \displaystyle E_{n} = \frac{1 + \sum_{k=1}^{n-1} P(n,k)E_{k}}{(1- P(n,n))}
Was benötigt wird, ist "Wahrscheinlichkeit, wie viele Personen noch gewinnen müssen" und "erwarteter Wert für die Anzahl der Personen, die gewonnen haben", aber da "erwarteter Wert für die Anzahl der Personen, die gewonnen haben" rekursiv berechnet wird. Berechnen Sie die "Wahrscheinlichkeit, wie viele Personen noch gewinnen müssen".

"Wahrscheinlichkeit, wie viele Personen noch zu gewinnen sind" ist (wie viele Muster gibt es für jede verbleibende Person) / (alle Muster) Zählen Sie die Gesamtzahl der Muster für jeden verbleibenden Gewinner.

Das Zählen der Anzahl möglicher Zahlenkombinationen für jede verbleibende Anzahl von Gewinnern ist wie folgt.

1. Listen Sie die von allen angegebenen Zahlenkombinationen auf
2. Finden Sie heraus, wie viele Zahlenmuster aufgelistet sind
3. Finden Sie in den aufgezählten Zahlenmustern heraus, wie viele Personen noch zu gewinnen sind
4. Berechnen Sie die Gesamtzahl der Zahlenmuster für jede verbleibende Anzahl von Gewinnern Wenn Sie dies bisher tun können, können Sie die Wahrscheinlichkeit ermitteln, indem Sie sie durch die Gesamtzahl aller Muster dividieren, sodass Sie die Wahrscheinlichkeit für jede verbleibende Anzahl von Gewinnern ermitteln können.

Probability.py

# ------------------------------------------------------------------------------------------------------------
#
#Finden Sie die Wahrscheinlichkeit für jede verbleibende Anzahl von Gewinnern
#
# ------------------------------------------------------------------------------------------------------------
#
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):
        """
Finden Sie die Wahrscheinlichkeit für jede verbleibende Anzahl von Gewinnern
        Parameters
        ----------
        p :Die Anzahl der Teilnehmer
        n :Anzahl der von den Teilnehmern angegebenen Zahlen
        """
        self.p = p
        self.n = n

    def sum_patterns_by_winner(self):
        """
Aggregieren Sie die Anzahl der Kombinationsmuster für jede verbleibende Anzahl von Gewinnern
        Returns
        -------
        list[Anzahl der Gewinner] :Anzahl der Kombinationsmuster
        """
        #Machen Sie eine Liste der Gewinn / Verlust-Ergebnisse
        decomp_list = DecomposingAddends().decomposing(self.p, self.n, 0)

        #Bereiten Sie eine Liste vor, um die Anzahl der Muster für die Anzahl der Teilnehmer einzugeben(1 Herkunft)
        self.patterns = [0] * (self.p + 1)
        #Aus der Liste der Ergebnisse nach der Anzahl der verbleibenden Gewinner
        for l in decomp_list:
            patterns = Combinations(self.n, l).get()  #Ermitteln Sie aus dem Ergebnismuster die Anzahl der Muster, in denen es auftritt
            winners = count_numbers(l)                  #Holen Sie sich die Anzahl der verbleibenden Personen, um zu gewinnen
            self.patterns[winners] += patterns

        return self.patterns

    def culc(self):
        result = Probability.result_list[self.p, self.n]
        if result is not None:                              #Wenn Sie bereits berechnet haben, verwenden Sie diesen Wert
            return result

        patterns = self.sum_patterns_by_winner()
        total = self.n ** self.p
        self.probability = [0.0] * (self.p)             #Bereiten Sie eine Liste vor, um die Wahrscheinlichkeit für die Anzahl der Teilnehmer einzugeben
        for i in range(1, self.p):
            self.probability[i] = patterns[i] / total    #Finde die Wahrscheinlichkeit

        self.probability[0] = patterns[self.p] / total  #Der letzte (egal)Geschäfte in 0

        Probability.result_list[self.p, self.n] = self.probability
        #Speichern Sie das Berechnungsergebnis
        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))

Nachdem wir die Wahrscheinlichkeit jeder verbleibenden Anzahl von Gewinnern kennen, werden wir endlich den erwarteten Wert finden. Wie bereits erläutert, wird der erwartete Wert nach der folgenden Formel berechnet. \displaystyle E_{n} = \frac{1 + \sum_{k=1}^{n-1} P(n,k)E_{k}}{(1- P(n,n))}

ExpectedValue.py

# ------------------------------------------------------------------------------------------------------------
#
#Finden Sie den erwarteten Wert
#
# ------------------------------------------------------------------------------------------------------------
#
#
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:                                 #Beenden Sie, wenn es weniger als einen Gewinner gibt
            return 0.0
        elif p == 2:                                #Wenn es zwei Personen gibt, gibt es keine Übereinstimmung, also 1 von Janken.Adopt 5
            return 1.5
        else:
            probability = Probability(p, n).calculation()        #Liste der Gewinnchancen
            result = 1
            for i in range(1, p):
                probability_i = probability[i]         #Wahrscheinlichkeit, dass ich verbleibende Gewinner bin
                expected_value = self.process(i, n, dummy)
                expected_value = (probability_i * expected_value)
                result = result + expected_value

            result = result / (1 - probability[0])       # (1-Wahrscheinlichkeit, dass jeder überleben wird)Teilen durch

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

Zusammenfassung

Formatieren Sie es schließlich in eine Tabelle und suchen Sie das n mit dem niedrigsten erwarteten Wert für jedes p.

NKen.py

# ------------------------------------------------------------------------------------------------------------
#
#N Faust: 0 Spieler..(n-1)Ein Spiel, bei dem der Gewinner die Person ist, die die Zahl bis zu n und die Zahl mit der geringsten Anzahl von Personen angibt.
#Hier wird in N Faust untersucht, wie oft n optimal ist, wenn es p Personen gibt.
#
# ------------------------------------------------------------------------------------------------------------
#
from ExpectedValue import ExpectedValue

expected_value_obj = ExpectedValue()            #Objekt zur Berechnung des erwarteten Wertes

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

text = "|-|"
for n in range(2, maxP):
    text = text + "----|".format(n)             #Horizontale Spalte der Spalte
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)