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.
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
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
There are 5 patterns of, but this corresponds to the pattern of dividing 5 into 3 out of the numbers obtained by multiplying.
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.
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
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 =
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
Transformed and
By doing so, you will be able to find the expected value.
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)
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
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))
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))
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
P | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
A | 0 | 0 | 1 | 1 | 2 | 2 |
B | 1 | 2 | 2 | 0 | 0 | 1 |
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
P | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
A | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 2 | 0 | 0 |
B | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 2 | 0 | 0 | 0 |
C | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 2 | 0 | 0 | 0 | 0 |
D | 0 | 1 | 0 | 0 | 0 | 0 | 2 | 0 | 0 | 0 | 0 | 3 |
E | 1 | 0 | 0 | 0 | 0 | 2 | 0 | 0 | 0 | 0 | 3 | 0 |
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.
Numbers issued by 4 people | Numbers issued by one person |
---|---|
0 | 1 |
0 | 2 |
1 | 0 |
1 | 2 |
2 | 0 |
2 | 1 |
So this can be represented by $ _ {3} P_ {2} = 6 $.
Therefore,
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.
a0 | a1 | a2 |
---|---|---|
0 | 1 | 2 |
0 | 2 | 1 |
1 | 0 | 2 |
1 | 2 | 0 |
2 | 1 | 0 |
2 | 0 | 1 |
In the combination of, A, B, C, D, E, F 5 people
a0 | a1 | a2 |
---|---|---|
A,B,C | D | E |
A,B,C | E | D |
If you think about the two patterns of
a0 | a1 | a2 |
---|---|---|
A,B,C | D | E |
a0 | a1 | a2 |
---|---|---|
0 | 1 | 2 |
Then
A | B | C | D | E |
---|---|---|---|---|
0 | 0 | 0 | 1 | 0 |
It will be
a0 | a1 | a2 |
---|---|---|
A,B,C | E | D |
a0 | a1 | a2 |
---|---|---|
0 | 2 | 1 |
Even at that time
A | B | C | D | E |
---|---|---|---|---|
0 | 0 | 0 | 1 | 0 |
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))
Formula to find the expected value
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.
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.
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))
Finally, format it into a table, and find the n with the lowest expected value for each p.
p\n | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
p= 3 n= 2[1.333] | 1.333 | 1.500 | ||||||||||||||||||||||||||
p= 4 n= 2[2.000] | 2.000 | 2.250 | 2.458 | |||||||||||||||||||||||||
p= 5 n= 3[1.762] | 2.067 | 1.762 | 1.952 | 2.275 | ||||||||||||||||||||||||
p= 6 n= 3[1.734] | 2.595 | 1.734 | 2.043 | 2.431 | 2.787 | |||||||||||||||||||||||
p= 7 n= 3[1.968] | 2.257 | 1.968 | 2.046 | 2.339 | 2.712 | 3.120 | ||||||||||||||||||||||
p= 8 n= 4[1.890] | 2.659 | 2.036 | 1.890 | 2.207 | 2.643 | 3.075 | 3.480 | |||||||||||||||||||||
p= 9 n= 4[1.860] | 2.643 | 2.179 | 1.860 | 2.137 | 2.572 | 3.031 | 3.490 | 3.949 | ||||||||||||||||||||
p=10 n= 4[1.978] | 3.012 | 2.247 | 1.978 | 2.093 | 2.486 | 2.961 | 3.436 | 3.888 | 4.317 | |||||||||||||||||||
p=11 n= 5[2.014] | 2.875 | 2.294 | 2.051 | 2.014 | 2.373 | 2.866 | 3.370 | 3.862 | 4.342 | 4.817 | ||||||||||||||||||
p=12 n= 5[1.979] | 3.197 | 2.401 | 2.119 | 1.979 | 2.275 | 2.765 | 3.292 | 3.805 | 4.295 | 4.761 | 5.207 | |||||||||||||||||
p=13 n= 5[2.014] | 3.208 | 2.467 | 2.173 | 2.014 | 2.202 | 2.661 | 3.200 | 3.735 | 4.249 | 4.746 | 5.230 | 5.709 | ||||||||||||||||
p=14 n= 5[2.076] | 3.513 | 2.598 | 2.263 | 2.076 | 2.142 | 2.550 | 3.093 | 3.651 | 4.189 | 4.703 | 5.194 | 5.666 | 6.123 | |||||||||||||||
p=15 n= 6[2.103] | 3.271 | 2.746 | 2.340 | 2.134 | 2.103 | 2.444 | 2.980 | 3.556 | 4.116 | 4.649 | 5.160 | 5.654 | 6.139 | 6.618 | ||||||||||||||
p=16 n= 6[2.099] | 3.530 | 2.828 | 2.414 | 2.182 | 2.099 | 2.356 | 2.864 | 3.450 | 4.031 | 4.586 | 5.115 | 5.622 | 6.112 | 6.588 | 7.053 | |||||||||||||
p=17 n= 6[2.124] | 3.431 | 2.854 | 2.478 | 2.232 | 2.124 | 2.287 | 2.748 | 3.336 | 3.936 | 4.512 | 5.059 | 5.582 | 6.086 | 6.578 | 7.062 | 7.541 | ||||||||||||
p=18 n= 6[2.165] | 3.677 | 2.912 | 2.530 | 2.296 | 2.165 | 2.238 | 2.638 | 3.215 | 3.830 | 4.428 | 4.994 | 5.534 | 6.052 | 6.553 | 7.042 | 7.521 | 7.992 | |||||||||||
p=19 n= 6[2.208] | 3.528 | 2.933 | 2.602 | 2.367 | 2.208 | 2.213 | 2.539 | 3.092 | 3.716 | 4.333 | 4.920 | 5.477 | 6.009 | 6.522 | 7.022 | 7.512 | 7.996 | 8.475 | ||||||||||
p=20 n= 7[2.210] | 3.756 | 2.908 | 2.692 | 2.441 | 2.251 | 2.210 | 2.457 | 2.971 | 3.596 | 4.230 | 4.837 | 5.412 | 5.959 | 6.485 | 6.995 | 7.492 | 7.981 | 8.462 | 8.936 | |||||||||
p=21 n= 7[2.226] | 3.708 | 2.923 | 2.778 | 2.509 | 2.295 | 2.226 | 2.394 | 2.855 | 3.470 | 4.118 | 4.745 | 5.339 | 5.902 | 6.441 | 6.961 | 7.468 | 7.964 | 8.454 | 8.938 | 9.418 | ||||||||
p=22 n= 7[2.253] | 3.932 | 2.940 | 2.847 | 2.570 | 2.346 | 2.253 | 2.350 | 2.748 | 3.343 | 3.999 | 4.645 | 5.258 | 5.838 | 6.390 | 6.922 | 7.438 | 7.942 | 8.438 | 8.926 | 9.408 | 9.886 | |||||||
p=23 n= 7[2.286] | 3.790 | 2.926 | 2.904 | 2.630 | 2.403 | 2.286 | 2.326 | 2.654 | 3.216 | 3.874 | 4.536 | 5.168 | 5.766 | 6.333 | 6.877 | 7.403 | 7.916 | 8.418 | 8.912 | 9.401 | 9.885 | 10.367 | ||||||
p=24 n= 8[2.320] | 3.997 | 2.949 | 2.955 | 2.692 | 2.467 | 2.322 | 2.320 | 2.576 | 3.094 | 3.745 | 4.420 | 5.071 | 5.687 | 6.270 | 6.827 | 7.363 | 7.884 | 8.394 | 8.894 | 9.388 | 9.876 | 10.360 | 10.840 | |||||
p=25 n= 8[2.327] | 3.935 | 2.991 | 2.994 | 2.760 | 2.532 | 2.360 | 2.327 | 2.515 | 2.979 | 3.613 | 4.297 | 4.966 | 5.601 | 6.200 | 6.770 | 7.318 | 7.848 | 8.365 | 8.872 | 9.371 | 9.865 | 10.353 | 10.838 | 11.320 | ||||
p=26 n= 8[2.345] | 4.137 | 2.985 | 3.017 | 2.829 | 2.597 | 2.402 | 2.345 | 2.471 | 2.875 | 3.483 | 4.169 | 4.854 | 5.507 | 6.124 | 6.708 | 7.268 | 7.807 | 8.333 | 8.846 | 9.351 | 9.850 | 10.343 | 10.831 | 11.316 | 11.797 | |||
p=27 n= 8[2.369] | 4.041 | 3.011 | 3.033 | 2.895 | 2.660 | 2.450 | 2.369 | 2.444 | 2.783 | 3.355 | 4.037 | 4.735 | 5.406 | 6.041 | 6.640 | 7.212 | 7.762 | 8.296 | 8.817 | 9.328 | 9.831 | 10.329 | 10.821 | 11.310 | 11.795 | 12.279 | ||
p=28 n= 8[2.398] | 4.233 | 3.054 | 3.049 | 2.957 | 2.723 | 2.502 | 2.398 | 2.431 | 2.706 | 3.233 | 3.903 | 4.610 | 5.299 | 5.951 | 6.567 | 7.152 | 7.713 | 8.255 | 8.783 | 9.301 | 9.810 | 10.312 | 10.808 | 11.301 | 11.789 | 12.275 | 12.758 | |
p=29 n= 8[2.430] | 4.199 | 3.058 | 3.066 | 3.013 | 2.787 | 2.558 | 2.430 | 2.431 | 2.645 | 3.120 | 3.769 | 4.480 | 5.184 | 5.854 | 6.487 | 7.086 | 7.658 | 8.210 | 8.746 | 9.270 | 9.785 | 10.292 | 10.793 | 11.289 | 11.781 | 12.270 | 12.756 | 13.240 |
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)
Recommended Posts