[PYTHON] The story of finding the optimal n in N fist

What is N fist?

When there are a lot of people, it's hard to win or lose even if you play rock-paper-scissors, and I think everyone has the experience of taking a long time. If you go around this with "rock-paper-scissors expected value", you will find many articles, so I will omit the explanation, but On the Average number of times to decide one person with rock-paper-scissors page, one winner is decided for 2 to 50 people. The average number of times up to is listed. Looking at this, when there were 8 people, it was already 12.1 times, exceeding 10 times.

In this way, when there are a large number of people, it is difficult to play a game, but in order to solve this, we will consider N fists.

N-Fist is a game in which participants voluntarily exchange one of the N numbers from 0 to (N-1), and the person who gives the smallest number is the winner. For example, there are 5 participants, and one of the three numbers up to 0.2 is given, and as a result, 2,0,2,1,0 and 1 are given when the numbers are given. One person is the least, so the person who gives 1 is the winner. With this rule, when you are two people, you can never win or lose. Therefore, the minimum number of people is three.

According to my research so far, if N is 3, there seems to be something called "gamer rock-paper-scissors". When N is 5, there seems to be something called "one-shot rock-paper-scissors". Also, at first, I named this game "Several Fists", but it seems that it existed in the Meiji era by another rule. Next, I named it "Numerical Fist", which seems to exist in China.

In this paper, the goal of this N-fist is to calculate the optimum N value (that is, one winner is determined by the minimum number of times) when there are p participants. As already mentioned, if two people remain at the end, there will be no win or loss, so we will adopt the expected value of 1.5 for rock-paper-scissors.

Combination of the number of numbers issued

For example, if there are 5 participants and N is 3, the hand that each participant will take is It will be $ 3 ^ 5 $. This is clear from the fact that the sequence of ternary numbers from 00000 to 22222 is 100000 in ternary, or $ 3 ^ 5 $. In other words, when p people compete with N numbers, the sequence of numbers given by each participant is N^p
It will be on the street.

Also, when counting the numbers of 0, 1, and 2 as to how many people put them out, The combination is the same as the combination of numbers obtained by multiplying p. We'll call this a "result pattern" for your convenience later.

For example, in the above example

1. 5 people give the same number
2. 4 people give the same number, 1 person gives a different number
3. 3 people give the same number, 2 people give different numbers
4. 3 people give the same number, 2 people give different numbers
5. Two people give the same number, two people give different numbers, and one person gives the remaining numbers

There are 5 patterns of, but this corresponds to the pattern of dividing 5 into 3 out of the numbers obtained by multiplying.

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

The expected value is determined by "probability of occurrence x value when it occurs". By finding the probability of occurrence of this result pattern, the expected value can be found. To find the probability of occurrence of the result pattern is, in other words, to find how many patterns are in this pattern out of all $ N ^ p $ times.

Expected value when the game is repeated

In this game, one winner is not always decided at one time. In the above example, if there is one person who gave 1 and one person who gave 2, both the person who gave 1 and the person who gave 2 will be the winners, and the two will play the game again. .. However, in the case of two people, there is no victory or defeat, so the final decision will be rock-paper-scissors. In the above example, 4) is this case. In 3) as well, there are two winners because the two are giving the numbers that were given less.

If 7 participants compete with N = 3, for example 7=3+2+2
In the combination of, there will be 4 winners.

These winners will play the game again and narrow down the winners.

For the expected value of the number of games to be repeated by extracting this winner, see the article Calculate the average number of times until the end of rock-paper-scissors. There is an explanation E_n = \sum_{k=1}^{n} P(n,k)(E_{k}+1)
Will be.

$ E_n $ is the expected value when the number of people is n, and P (n, k) is the probability when k people win when the number of people is n. This formula can be transformed into $ E_n = 1 + \ sum_ {k = 1} ^ {n} P (n, k) E_ {k} $.

Even if you don't know the mathematical proof of this formula, if it is this formula "The expected value $ E_n $ is ($ E_n = ), try it once (1 +), and the probability that there will be k winners (P (n, k)), if you win more with that number of people Multiply the expected value of ( E_ {k}) $ and add the cases of all the remaining people ($ \ sum_ {k = 1} ^ {n} $) ", so I think it is easy to understand. I will.

As it is, the term of k = n is on the right side and $ E_ {n} $ exists on both the left and right sides, and if you build the logic as it is, it will be an infinite recursive process. This further

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

Transformed and

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

By doing so, you will be able to find the expected value.

Recursive processing

From now on, we will create a process to find the expected value, but during the process from now on, recursive processing will appear many times. The calculation of the lower value is called many times from the upper, but it is a waste of processing speed to perform the exact same calculation, so once it is calculated, prepare one that returns the calculation result immediately from the next time. I will do it.

Also, to implement this process, create a list that does not make an exception even if you access outside the range of the list in which the value is set.

ExpandList.py

# ------------------------------------------------------------------------------------------------------------
#
#Automatically expands when accessed outside the list
#
#Mr. shiracamus explained how to realize by inheriting list.
#Thank you very much.
#I rewrote it accordingly.
#
# ------------------------------------------------------------------------------------------------------------
#


class ExpandList(list):
    def __setitem__(self, i, value):
        """
Set the value at the specified position
        Parameters
        ----------
        i :Subscript
        value :Value to set
        """
        if i >= len(self):
            self.extend([None] * (i - len(self) + 1))
        super().__setitem__(i, value)

    def __getitem__(self, i):
        """
Get the value from the specified location
        Parameters
        ----------
        i :Subscript

        Returns :
        -------
            (When within range) :Value at the specified position
            (When out of range) : None
        """

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


class ExpandList2D(ExpandList):
    def __setitem__(self, pos, value):
        """
Set the value at the specified position
        Parameters
        ----------
        pos :Subscript
        value :Value to set
        """

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

    def __getitem__(self, pos):
        """
Get the value from the specified location
        Parameters
        ----------
        pos :Subscript
        Returns :
        -------
            (When within range) :Value at the specified position
            (When out of range) : 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])

The above process returns None when reading out of range for 1D and 2D lists, and get () which returns stored values otherwise. If you specify outside the range and store it, the list is expanded and stored. ~~ It doesn't inherit the list and isn't an iterator, but it's implemented because it's good enough for this use. ~~

~~ Since it's about Python, there may already be something more useful, but I couldn't find it after a while, so I'll just use it. ~~ I received a comment from @shiracamus and changed it to inherit from list.

Next, create a class that returns the saved value if it has already been calculated, and recursively calls the method if it has not been calculated yet.

ProcessWithMemory.py

# ------------------------------------------------------------------------------------------------------------
#
#Processing once calculated returns the result without calculation
#
# ------------------------------------------------------------------------------------------------------------
#
from ExpandList import ExpandList2D


class Container:
    def __init__(self):
        """
Container to store values
        """
        self.value = None

    def get(self):
        """
Get the stored value
        Returns
        -------
Saved value
        """
        return self.value

    def set(self, data):
        """
Save value
        Parameters
        ----------
        data :Value to save
        """
        self.value = data


class ProcessWithMemory:
    def __init__(self, function):
        """
A class that returns the saved value, if any, and calls the process otherwise
        """
        self.value = ExpandList2D()
        self.check_process = function

    def process(self, i, j, *args):
        """
Checks if it has already been calculated, returns the value if it does, calls the registered method if not
        Parameters
        ----------
        i :Subscript 1D
        j :Subscript 2D
        kwargs :Variadic argument

        Returns
        -------
Result value
        """
        stored_value = self.value[i,
                                  j]                      #Retrieve the results stored in the list
        if stored_value is not None:
            return stored_value.get()                      #If so, return it

        data = self.check_process(i, j, args)             #Call process and get result

        container = Container()                             #Prepare a container to store the result
        container.set(data)                               #Store the result in a container
        #Save the container (I don't save it directly because I want to save None as well)
        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)

Combination of the number of numbers given by everyone

As explained at the beginning, when counting the numbers given by all the participants, the pattern of how many people gave the same number is Arithmetic. It will be keirinkan / sansu / WebHelp / 01 / page1_14.html). Since P (n, k) required to calculate the expected value is (the number of combinations of numbers that form the pattern) / (the number of combinations of all numbers), You need to find out what the pattern is, how many patterns there are, and the number of all number combinations. As already explained, the number of all number combinations is known to be $ N ^ p $ when p people compete with N numbers. Find out what the remaining patterns are and how many of them there are.

In this section, we will identify all the patterns.

When 5 is aggregated

1. ５
2. ４＋１
3. ３＋２
4. ３＋１＋１
5. ２＋２＋１
6. ２＋１＋１＋１
   Can be disassembled into.

This can be thought of as the process of subtracting m from 5 and further decomposing the rest. Also, when N = 3, it is too much to decompose into 4 pieces, so in this case 2 + 1 + 1 + 1 of 6) is not necessary, and 1) to 5) are sufficient.

Below is a class of DecomposingAddends that can be added and decomposed to identify combinations of numbers.

DecomposingAddends.py

# ------------------------------------------------------------------------------------------------------------
#
#Additive decomposition
#   N = i0+i1+i2...Find a combination that becomes
#
# ------------------------------------------------------------------------------------------------------------
#
#
from ProcessWithMemory import ProcessWithMemory


class DecomposingAddends(ProcessWithMemory):
    def __init__(self):
        """
Additive decomposition: Since the process is recursive, use ProcessWithMemory to return the result if it has already been calculated.
        """
        super().__init__(self.decomposing)

    def decomposing(self, p, n, dummy):
        """
Additive decomposition
        Parameters
        ----------
        p :Number of minutes to be added
        n :Maximum number of divisions
        dummy :Dummy argument (unused) when using ProcessWithMemory)

        Returns
        -------
List of aggregate results
        """
        if n == 0 and p > 0:            #None when the length exceeds n but there is a rest
            return None
        if p == 0:                      #Disassembled to the end
            return [[]]
        elif p == 1:                    #The rest is 1
            return [[1]]
        else:
            ret_list = [[p]]  #The first list is p itself
            for i in range(p - 1, 0, -1):  # p-1 ..Loop to 1
                remain = p - i          #Remaining number
                lower_list = self.process(remain, n - 1, 0)
                #Further add and decompose with the remaining number
                if lower_list is None:  #The result exceeds the maximum number of divisions
                    continue            #Ignore this result
                #Make a list with the remaining number
                for low in lower_list:  #A list of the remaining numbers
                    if low[0] <= i:     #Patterns larger than i are duplicated and removed
                        l1 = [i]        #Otherwise, i is at the beginning and the addition decomposition result by the remaining numbers is added at the end.
                        l1.extend(low)
                        ret_list.append(l1)
                        #Register in the result list
            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))

Count the number of winners

In N-fist, the winner is the one who gives the smallest number, so find the minimum value and the sum of those values from the list obtained above. Above p = 7 n = 3 list = [[7], [6, 1], [5, 2], [5, 1, 1], [4, 3], [4, 2, 1], [ In the case of 3, 3, 1], [3, 2, 2]] [7] ・ ・ ・ ・ ・ All 7 people [6, 1] ・ ・ ・ Only one person was different, so one person [5, 2] ・ ・ ・ Two people because they gave different results [5, 1, 1] ・ ・ Two people gave different ones [4, 3] ・ ・ ・ 3 people because they gave different results [4, 2, 1] ・ ・ One of the three types is the smallest, so one [3, 3, 1] ・ ・ One of the three types is the smallest, so one [3, 2, 2] ・ ・ Of the three types, two are two, so four. Will be.

This is calculated by tracing from the back of the list and adding until a value greater than the last value is obtained.

count_numbers.py

# ------------------------------------------------------------------------------------------------------------
#
#Count the number of people who put out the smallest number in the list
#
# ------------------------------------------------------------------------------------------------------------
#
#


def count_numbers(terget_list):
    """
Find the sum of the smallest numbers in the list
    Parameters
    ----------
    terget_list :Target list

    Returns
    -------
Total value of the smallest number
    """
    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))

Find out how many combinations of numbers there are

From the above, it is now possible to find the combination pattern of numbers when playing with p people and the number of winners. Count how many patterns the combination of numbers obtained so far is actually a combination of numbers from 0 to (n-1).

For example, if p = 2 people, n = 3, and the result of victory or defeat is [1,1]. The number given is 0.2, so If players are A and B respectively, and the pattern that the result of victory or defeat is [1,1] is listed

It will be 6 patterns of

This is when p = 5 people, n = 3, and the result of victory or defeat is [4,1]. The number given is 0.2, so

And, although it continues, there are 30 ways as a result.

From now on, it is calculated that there are 6 ways for p = 2 people, n = 3 and [1,1], and 30 ways for p = 5 people, n = 3 and [4,1]. Make it as requested.

If p = 5, n = 3, and [4,1], this means that 4 people gave the same number and only 1 person gave a different number. It is a combination that extracts 4 out of 5 people as to which 4 out of 5 people gave the number. $ _ {5} C_ {4} = 5 $. The one who gave the remaining one number is the other person, so there are five ways in total. On the other hand, considering the pattern of which number was given by 4 people and which number was given by 1 person, Since N = 3, it can be said that it is a permutation in which two of the three types of numbers are taken out and arranged.

So this can be represented by $ _ {3} P_ {2} = 6 $.

Therefore,

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

Will be.

When p = 5 people, n = 3, and [3,1,1], The combination of three people who give the same number is $ _ {5} C_ {3} $. The rest gave different numbers for each person, but the combination that the second number can take is Three out of five have already been put out and two are left, and one of them will be decided, so $ _ {2} C_ {1} = 2 $. The remaining one is decided automatically, so $ _ {5} C_ {3} ☓ _ {2} C_ {1} = 20 $ That's right.

As for which number was given, if [3,1,1] is [a0, a1, a2], Since a0, a1, and a2 are the number of permutations that can be taken, it seems to be $ _ {3} P_ {3} = 6 $ (I thought so), You will end up counting a1 and a2, which are one each, in duplicate.

In the combination of, A, B, C, D, E, F 5 people

If you think about the two patterns of

Then

It will be

Even at that time

Will have the same result as.

Therefore, it is necessary to eliminate this duplicate case.

To consider how to handle this duplication, let's take the case of P = 6, N = 4. In this case, there is a pattern of [a0, a1, a2, a3] = [2,2,1,1] in which four numbers are output.

In this pattern, the combination of patterns in which 6 people give each number of a0, a1, a2, a3 $ _ {6} C_ {2} ☓ _ {4} C_ {2} ☓ _ {2} C_ {1} = 180 $ That's right.

Also, For who issued the numbers for a0, a1, a2, and a3, Because it is a permutation that assigns the numbers 0..3 to a0, a1, a2, a3 $ _ {4} P_ {4} = 24 $ That's right.

However, when "the person (A, B) issues [0] and the person (C, D) issues [1]" and "the person (C, D) issues [1]" (A) , B) person issued [0] "is the same and duplicate The combination of x and y assigned to a0 and a1 is the same as the combination of y and x assigned to a0 and a1, that is, $ _ {2} P_ {2} $ is duplicated. Since a2 and a3 are the same, the combination of numbers assigned to [a0, a1, a2, a3] is $ \ frac {_ {4} P_ {4}} {_ {2} P_ {2} ☓ _ {2 There are 6 ways of} P_ {2}} $.

Therefore, in the case of [2,2,1,1], the combination of all numbers is $ \ frac {_ {6} C_ {2} ☓ _ {4} C_ {2} ☓ _ {2} C_ {1 } ☓ _ {4} P_ {4}} {_ {2} P_ {2} ☓ _ {2} P_ {2}} = 1080 $ That's right.

In the case of [3,1,1,1], a1, a2, and a3 are all 1, which is a duplicate. In this pattern, the combination of patterns in which 6 people give each number of a0, a1, a2, a3 $ _ {6} C_ {3} ☓ _ {3} C_ {1} ☓ _ {2} C_ {1} = 120 $ For who issued the numbers for a0, a1, a2, and 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 $ That's right.

Based on the above consideration, we created a code to find the number of patterns when the number of each number is [a0, a1, a2, a3] when one p person comes out of N numbers. I will.

Combinations.py

# ------------------------------------------------------------------------------------------------------------
#
#The number of appearances of each number[a0,a1..am]Find the total number of combinations of numbers when
#
# ------------------------------------------------------------------------------------------------------------
#
from scipy.special import perm, comb          #For calculating permutation combinations


class Combinations:

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

    def redundancy(self):
        """
Calculate the number to be removed due to duplication
        Parameters
        ----------
        Returns
        -------
Number to be divided due to duplication
        """
        current_value = 0                       #Number to check for duplicates
        counter = 0                             #The number of that number
        result = 1                              #result
        for i in self.terget_list:
            if current_value != i:
                p = perm(counter, counter)      # cPc :Number of duplicate patterns
                result = result * p             #Multiply by the number of previous duplicate patterns
                counter = 1                     #Because there is one
                current_value = i               #Next number to check for duplicates
            else:
                counter += 1                    #The same number continues

        p = perm(counter, counter)              #Last operation on the last value
        result = result * p
        return result

    def player_combinations(self):
        """
Find the permutation of patterns that participants can take
        Parameters
        ----------
        n :Range of values
        terget_list :List to check (pattern of how many each number was issued)

        Returns
        -------
Number of permutations of patterns that participants can take
        """
        length = len(self.terget_list)               #How many numbers were given
        permut = perm(self.n, length)                #Permutation of the numbers issued out of all the numbers
        result = permut / self.redundancy()          #Remove duplicates
        return result

    def number_combinations(self):
        """
Get the number of combinations of numbers
        Returns
        -------
Number of combinations of numbers
        """
        remain = sum(self.terget_list)                      #Ask for the number of participants
        result = 1                                          #Initial value of result
        for i in self.terget_list:
            #Combination when i people give the same number
            combin = comb(remain, i)
            result = result * combin                        #Infinite product
            remain = remain - i                             #Remaining number of people

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

Count the number of patterns for each number of winners

Formula to find the expected value \displaystyle E_{n} = \frac{1 + \sum_{k=1}^{n-1} P(n,k)E_{k}}{(1- P(n,n))}
What is needed in is "probability of how many people have survived" and "expected value for the number of survivors", but since "expected value for the number of survivors" is recursively calculated Calculate the "probability of how many people are left to win".

"Probability of how many people are left to win" is (how many patterns are there for each remaining number of people) / (all patterns) Count the total number of patterns for each remaining winner.

The process of counting the number of possible combinations of numbers for each remaining number of winners is as follows.

1. List the combinations of numbers given by everyone
2. Find out how many patterns of numbers are listed
3. Find out how many people are left to win in the enumerated number patterns
4. Calculate the total number of number patterns for each remaining number of winners If you can do so far, the probability can be obtained by dividing by the total number of all patterns, so you can get the probability for each remaining number of winners.

Probability.py

# ------------------------------------------------------------------------------------------------------------
#
#Find the probability for each remaining number of winners
#
# ------------------------------------------------------------------------------------------------------------
#
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):
        """
Find the probability for each remaining number of winners
        Parameters
        ----------
        p :The number of participants
        n :Number of numbers given by participants
        """
        self.p = p
        self.n = n

    def sum_patterns_by_winner(self):
        """
Aggregate the number of combination patterns for each remaining number of winners
        Returns
        -------
        list[Number of winners] :Number of combination patterns
        """
        #Make a list of win / loss results
        decomp_list = DecomposingAddends().decomposing(self.p, self.n, 0)

        #Prepare a list to enter the number of patterns for the number of participants(1 origin)
        self.patterns = [0] * (self.p + 1)
        #From the list of results, by the number of remaining winners
        for l in decomp_list:
            patterns = Combinations(self.n, l).get()  #From the result pattern, get the number of patterns in which it occurs
            winners = count_numbers(l)                  #Get the number of people left to win
            self.patterns[winners] += patterns

        return self.patterns

    def culc(self):
        result = Probability.result_list[self.p, self.n]
        if result is not None:                              #If you have already calculated, use that value
            return result

        patterns = self.sum_patterns_by_winner()
        total = self.n ** self.p
        self.probability = [0.0] * (self.p)             #Prepare a list to enter the probability for the number of participants
        for i in range(1, self.p):
            self.probability[i] = patterns[i] / total    #Find the probability

        self.probability[0] = patterns[self.p] / total  #The last one (all the same)Stores in 0th

        Probability.result_list[self.p, self.n] = self.probability
        #Save the calculation result
        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))

Now that we know the probability of each remaining winner, we will finally find the expected value. The expected value is calculated by the following formula as already explained. \displaystyle E_{n} = \frac{1 + \sum_{k=1}^{n-1} P(n,k)E_{k}}{(1- P(n,n))}

ExpectedValue.py

# ------------------------------------------------------------------------------------------------------------
#
#Find the expected value
#
# ------------------------------------------------------------------------------------------------------------
#
#
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:                                 #End if there is less than one winner
            return 0.0
        elif p == 2:                                #When there are two people, there is no match, so 1 of rock-paper-scissors.Adopt 5
            return 1.5
        else:
            probability = Probability(p, n).calculation()        #List of probabilities that the remaining winners will be i
            result = 1
            for i in range(1, p):
                probability_i = probability[i]         #Probability that the remaining winners will be i people
                expected_value = self.process(i, n, dummy)
                expected_value = (probability_i * expected_value)
                result = result + expected_value

            result = result / (1 - probability[0])       # (1-Probability that everyone will survive)Divide by

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

Summary

Finally, format it into a table, and find the n with the lowest expected value for each p.

NKen.py

# ------------------------------------------------------------------------------------------------------------
#
#N fist: 0 players..(n-1)A game in which the winner is the person who gives the number up to n and gives the number with the smallest number.
#Here, in N fist, when there are p people, how many times n is optimal is investigated.
#
# ------------------------------------------------------------------------------------------------------------
#
from ExpectedValue import ExpectedValue

expected_value_obj = ExpectedValue()            #Object to calculate the expected value

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

text = "|-|"
for n in range(2, maxP):
    text = text + "----|".format(n)             #Horizontal line of column
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)