N拳とは
ちょっと人数が多い時、じゃんけんしてもなかなか勝敗がつかず、長い時間がかかった経験は、誰にでもあると思います。
これについては「じゃんけん 期待値」でぐぐると、たくさん記事が見つかるので説明は割愛しますが、
じゃんけんで1人を決めるまでの平均回数のページには、2人から50人までについて、勝者が1人に決まるまでの、平均回数が記載されています。
これを見ると8人の時に、既に12.1回となり10回を超えています。
このように、多人数になると、勝負がなかなかつかないじゃんけんですが、これを解決する為にN拳というものを考えます。
N拳は、0から(N-1)までのN個の数字のうちの一個を、参加者が任意で出し合い、一番出された数の少ない数字を出した人を勝者とするゲームです。
例えば、5人の参加者がいて、0..2までの3個の数字のうち、一個を出すこととし、その結果それぞれ2,0,2,1,0と、数字を出した時には1が１人で一番少ないですから、１を出した人が勝者となります。
このルールでは、２人の時は、絶対に勝敗が付きません。
ですから、最低人数は３人という事になります。
今まで調べたところ、Nが３の場合は「ゲーマーじゃんけん」というものが存在しているようです。
Nが5の場合には「一発ジャンケン」という名前のものがあるみたいです。
また、最初に、このゲームの名前を「数拳」にしたのですが、これは別のルールで明治時代に存在していたようです。
次に「数字拳」という名前にしたのですが、これは中国に存在しているようです。
本稿では、このN拳について、参加者がp人の時に最適な（すなわち、最低回数で１人の勝者が決まる)Nの値を算出する事を目標とします。
なお、既に述べた通り、最後に２人が残った場合は勝敗はつかないので、じゃんけんの期待値1.5を採用する事にします。
出される数字の数の組み合わせ
例えば参加者が5人で、Nが３の場合、各参加者が出す手は
$3^5$通りになります。
これは、3進法の数値の00000から22222までの数値の並びが３進法で100000、すなわち$3^5$である事から明らかです。
すなわちp人の人がN個の数字で勝負する場合、各参加者が出す数字の並びは
$N^p$
通りになります。
また、0,1,2それぞれの数字を、何人の人が出したかにをカウントした時、
その組み合わせは、pを加数分解した数字の組み合わせと同じになります。
あとで説明する時に便利なように、これを「結果パターン」と名付けます。
例えば、上記の例では、
1) 5人が同じ数字を出す
2) 4人が同じ数字を出して、1人が違う数字を出す
3) 3人が同じ数字を出して、2人が違う数字を出す
4) 3人が同じ数字を出して、2人がそれぞれ違う数字を出す
5) 2人が同じ数字を出して、2人が違う数字を出し、残った数字を1人が出す
の５パターンになりますが、これは、５を加数分解した数字のうち、３つに分けるパターンに相当します。
1) 5 = 5
2) 5 = 4 + 1
3) 5 = 3 + 2
4) 5 = 3 + 1 + 1
5) 5 = 2 + 2 + 1
期待値は、「それが発生する確率 X それが起こった時の値」で決まりますから、
この結果パターンの発生確率を求める事により、期待値を求める事が出来ます。
結果パターンの発生確率を求めるとは、言い換えれば、全$N^p$回のうち、このパターンになるのが何パターンあるのかを求めるという事になります。
勝負を繰り返した時の期待値
このゲームでは、１回で１人の勝者が決まるとは限りません。
上記の例では1を出した人が1人で2を出した人が1人の場合、1を出した人も2を出した人も勝者となり、2人で再度ゲームをする事になります。
もっとも、２人の場合は勝敗が付きませんから、最後はジャンケンで決める事になります。
上記の例では、4)がこのケースにあたります。
3)においても、2人が少なく出された数字を出しているわけですから、勝者は2人です。
7人の参加者がN=3で勝負した場合、例えば
7=3+2+2
の組み合わせになれば、勝者は4人になります。
この勝者同士が、再度ゲームを行い、さらに勝者を絞り込んでいきます。
この勝者を抜き出し繰り返されるゲームの回数の期待値については、じゃんけんが終わるまでの平均回数を求めるの記事に説明がありますが
$E_n = \sum_{k=1}^{n} P(n,k)(E_{k}+1)$
になります。
$E_n$は、人数がn人の時の期待値、P(n,k)は、人数がn人の時、k人勝ち抜ける時の確率です。
この式は、$E_n = 1 + \sum_{k=1}^{n} P(n,k)E_{k}$に変形出来ます。
この式の数学的証明がわからなくても，この式であれば
「期待値$E_n$は($E_n =$)、とりあえず一回やってみて(1 +) 、勝者がk人になる確率(P(n,k))に、その人数で、さらに勝負した場合の期待値($E_{k})$をかけたものを、全ての残り人数ののケース分加算する($ \sum_{k=1}^{n}$)」なので、理解しやすいと思います。
このままでは、k=nの項が右辺にあって$E_{n}$が左右両方に存在して、このままロジックを組むと無限の再帰処理になりますので、
これをさらに
$E_n = 1 + \sum_{k=1}^{n-1} P(n,k)E_{k} + P(n,n)E_{n}$
と変形し、
$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))}$
とする事で、期待値を求める事が出来るようになります。
再帰処理
これから、期待値を求める処理を作成するわけですが、これからの処理中、再帰処理が何度も出てきます。
下位の値の計算は、上位から何度も呼ばれますが、全く同じ計算を行うのは処理速度の無駄ですので、一度計算した場合は、次からは計算結果をすぐに返すものを用意する事にします。
また、この処理を実装するのに、値がセットされたリストの範囲外にアクセスしても、例外にならないリストも作っておきます。
# ------------------------------------------------------------------------------------------------------------
#
# リストの範囲外にアクセスされたら自動的に拡張する
#
# shiracamusさんより、listの継承で実現する方法をおしえて頂きました。
# ありがとうございます。
# それに従って書き換えました。
#
# ------------------------------------------------------------------------------------------------------------
#
class ExpandList(list):
def __setitem__(self, i, value):
"""
指定した位置に値をセットする
Parameters
----------
i : 添字
value : セットする値
"""
if i >= len(self):
self.extend([None] * (i - len(self) + 1))
super().__setitem__(i, value)
def __getitem__(self, i):
"""
指定された箇所から値を得る
Parameters
----------
i : 添字
Returns :
-------
(範囲内の時) : 指定された位置の値
(範囲外の時) : None
"""
return super().__getitem__(i) if i < len(self) else None
class ExpandList2D(ExpandList):
def __setitem__(self, pos, value):
"""
指定した位置に値をセットする
Parameters
----------
pos : 添字
value : セットする値
"""
y, x = pos
if super().__getitem__(y) is None:
super().__setitem__(y, ExpandList())
super().__getitem__(y)[x] = value
def __getitem__(self, pos):
"""
指定された箇所から値を得る
Parameters
----------
pos : 添字
Returns :
-------
(範囲内の時) : 指定された位置の値
(範囲外の時) : 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])
上記の処理は、１次元リストと２次元リストについて、範囲外を読みだしたらNoneを返し、それ以外は格納されている値を返すget()と、
範囲外を指定して格納したら、リストを拡張して格納するものです。
リストを継承していないし、イテレータでもありませんが、今回の用途には十分なので、この実装になっています。
Pythonの事なので、既にもっと便利なものが既に存在しているかもしれませんが、ちょっと探して見当たらなかったので、このまま使います。
@shiracamus様よりコメントを頂いて、listから継承するように変更しました。
次は、既に計算していたら保存してある値を返し、まだ計算していなければ再帰的にメソッドを呼び出すクラスを作ります。
# ------------------------------------------------------------------------------------------------------------
#
# 一度計算した処理は、計算せずに結果を返す
#
# ------------------------------------------------------------------------------------------------------------
#
from ExpandList import ExpandList2D
class Container:
def __init__(self):
"""
値を保存するコンテナ
"""
self.value = None
def get(self):
"""
保存されている値を得る
Returns
-------
保存されている値
"""
return self.value
def set(self, data):
"""
値を保存する
Parameters
----------
data : 保存する値
"""
self.value = data
class ProcessWithMemory:
def __init__(self, function):
"""
保存している値があれば、それを返し、なければ処理を呼び出すクラス
"""
self.value = ExpandList2D()
self.check_process = function
def process(self, i, j, *args):
"""
既に計算されているかどうかをチェックして、していれば値を返し、していなければ登録されているメソッドを呼び出す
Parameters
----------
i : 添字 1次元目
j : 添字 2次元目
kwargs : 可変長引数
Returns
-------
結果の値
"""
stored_value = self.value[i,
j] # リストに保存されている結果を取り出す
if stored_value is not None:
return stored_value.get() # されていれば、それを返す
data = self.check_process(i, j, args) # 処理を呼び出し結果を得る
container = Container() # 結果を格納するコンテナを用意する
container.set(data) # 結果をコンテナに格納する
# コンテナを保存する（直接保存しないのは、Noneも保存したいから）
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)
全員が出した数字の数の組み合わせ
最初に説明した通り、参加者全員が出した数を数えた時、何人の人が同じ数字を出したかのパターンは、加数分解になります。
期待値の計算に必要な、P(n,k)は、（そのパターンになる数字の組み合わせの数）/（全ての数字の組み合わせの数）ですから、
そのパターンとは何か、と、そのパターンがいくつあるか、および、全ての数字の組み合わせの数を求める必要があります。
既に説明した通り、全ての数字の組み合わせの数は、p人がN個の数字で勝負する場合、$N^p$と分かっていますので、
残りのそのパターンとは何かと、そのパターンがいくつあるかを求めます。
この節では、全てのパターンを洗い出す事をします。
５を加数分解すると、
1) ５
2) ４＋１
3) ３＋２
4) ３＋１＋１
5) ２＋２＋１
6) ２＋１＋１＋１
に分解出来ます。
これは、５からmを引き、残りを更に加数分解する処理と考える事が出来ます。
また、N=3の時、４つに分解するのは分解し過ぎですから、この場合6)の2+1+1+1は必要なくて、1）から5)までで十分だと言えます
下記に、加数分解して数字の組み合わせを洗い出すクラスDecomposingAddendsを示します
# ------------------------------------------------------------------------------------------------------------
#
# 加数分解
# N = i0+i1+i2...になる組み合わせを求める
#
# ------------------------------------------------------------------------------------------------------------
#
#
from ProcessWithMemory import ProcessWithMemory
class DecomposingAddends(ProcessWithMemory):
def __init__(self):
"""
加数分解する：処理は再帰になるので、ProcessWithMemoryを使って、既に計算していた場合はその結果を返すようにする
"""
super().__init__(self.decomposing)
def decomposing(self, p, n, dummy):
"""
加数分解する
Parameters
----------
p : 被加数分回数
n : 最大の分割数
dummy : ProcessWithMemoryを使う上でのダミー引数（未使用)
Returns
-------
加数分解した結果のリスト
"""
if n == 0 and p > 0: # 長さがnを超えたのに残りがある時はNone
return None
if p == 0: # 最後まで分解した
return [[]]
elif p == 1: # 残りが１になった
return [[1]]
else:
ret_list = [[p]] # 一番目のリストはp自身
for i in range(p - 1, 0, -1): # p-1 .. 1までループ
remain = p - i # 残りの数
lower_list = self.process(remain, n - 1, 0)
# 残りの数でさらに加数分解する
if lower_list is None: # 結果が最大分割数を超えた
continue # この結果は無視する
# 残った数で、リストを作る
for low in lower_list: # 残った数を加数分解したリスト
if low[0] <= i: # iより大きなパターンは、重複になるので除去
l1 = [i] # そうでなければ、iを先頭として、残りの数による加数分解結果を後ろにつける
l1.extend(low)
ret_list.append(l1)
# 結果リストに登録する
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))
勝者の人数を数える
N拳では、出した人数が一番少ない数字を出した人を勝者とするので、上記で求めたリストから、最小値と、その値の合計を求めます。
上記のp=7 n=3 list=[[7], [6, 1], [5, 2], [5, 1, 1], [4, 3], [4, 2, 1], [3, 3, 1], [3, 2, 2]]の場合は
[7]・・・・・ ７人全員
[6, 1] ・・・ 1人だけ違うのを出したので1人
[5, 2] ・・・ 2人だけ違うのを出したので2人
[5, 1, 1]・・ 1人だけ違うのを出した人が2人
[4, 3] ・・・ 3人違うのを出したので3人
[4, 2, 1]・・ 3種類出されたうち1人が最小なので1人
[3, 3, 1]・・ 3種類出されたうち1人が最小なので1人
[3, 2, 2]・・ 3種類出されたうち2人つづが２つなので4人
になります。
これは、リストの後ろの方からたどっていって、最後の値より大きな値が出るまでを加算していくことで求められます。
# ------------------------------------------------------------------------------------------------------------
#
# リストのうち、最小の数を出した人数を数える
#
# ------------------------------------------------------------------------------------------------------------
#
#
def count_numbers(terget_list):
"""
リストの中の、最小の数の合計を求める
Parameters
----------
terget_list : 対象となるリスト
Returns
-------
最小の数の合計値
"""
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))
数字の数の組み合わせが何通りあるかを調べる
以上により、p人で勝負した時の数字の組み合わせパターンと、勝者の人数を求める事が出来るようになりました。
これまでに求めた数字の数の組み合わせが、実際、0から(n-1)までの数字の組み合わせとして、何パターンあるのかを数えます。
たとえば、p=2人、n=3で、勝敗の結果が[1,1]の場合。出された数字は0..2ですから、
プレイヤーをそれぞれA、Bとし、勝敗の結果が[1,1]になるパターンを列挙すると
| P | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| A | 0 | 0 | 1 | 1 | 2 | 2 |
| B | 1 | 2 | 2 | 0 | 0 | 1 |
の６パターンになります
これが、p=5人、n=3で、勝敗の結果が[4,1]の場合。出された数字は0..2ですから、
| 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 |
と、まだまだ続きますが、結果的に30通りになります。
p=2人、n=3で[1,1]の場合は6通りで、p=5人、n=3で、[4,1]の場合が30通りになるという事を、これから計算で求められるようにします。
p=5人、n=3で、[4,1]の場合、これは4人が同じ数字を出して、１人だけ違う数字を出した事を意味します。
5人のうち、どの4人がその数字を出したか、については5人から4人を抽出する組み合わせですから
${5}C{4} = 5$になります。
残り１個の数字を出した１名は、それ以外の人なので、全部で5通りという事になります。
これに対し、4名がどの数字を出して1名がどの数字を出したか、のパターンについて考えると、
N=3ですから全部で３種類の数字の中から2つを取り出して並べる順列という事が言えます。
| 4人が出した数字 | １人が出した数字 |
|---|---|
| 0 | 1 |
| 0 | 2 |
| 1 | 0 |
| 1 | 2 |
| 2 | 0 |
| 2 | 1 |
で、これは${3}P{2} =6$で表す事が出来ます。
従って、
${5}C{4} ☓ {3}P{2} = 30$
になります。
p=5人、n=3で、[3,1,1]の場合、
同じ数を出す3人の組み合わせは、${5}C{3}$です。
残りは１人ずつ違う数字を出したわけですが、2番目の数字が取りうる組み合わせは、
5人のうち3人が既に出して2人残っていて、そのうちの１人を決めるわけですから${2}C{1}=2$になります。
残りの１人は、自動的に決まるので、
${5}C{3} ☓ {2}C{1} = 20$通りだと言えます。
どの数字を出したかについては、[3,1,1]を[a0,a1,a2]とすると、
a0,a1,a2が取りうる順列の数なので、${3}P{3}=6$に思えますが(自分はそう思った)、
それぞれ１個ずつであるa1とa2を重複して数えてしまう事になります。
| a0 | a1 | a2 |
|---|---|---|
| 0 | 1 | 2 |
| 0 | 2 | 1 |
| 1 | 0 | 2 |
| 1 | 2 | 0 |
| 2 | 1 | 0 |
| 2 | 0 | 1 |
の組み合わせでは、A,B,C,D,E,Fの5人が
| a0 | a1 | a2 |
|---|---|---|
| A,B,C | D | E |
| A,B,C | E | D |
の２つのパターンで考えてみると
| a0 | a1 | a2 |
|---|---|---|
| A,B,C | D | E |
| a0 | a1 | a2 |
|---|---|---|
| 0 | 1 | 2 |
ならば、
| A | B | C | D | E |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 |
になりますが、
| a0 | a1 | a2 |
|---|---|---|
| A,B,C | E | D |
| a0 | a1 | a2 |
|---|---|---|
| 0 | 2 | 1 |
の時も、
| A | B | C | D | E |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 |
と同じ結果になってしまいます。
従って、この重複したケースを除去する必要があります。
この重複をどう扱うのかを考えるために、P=6,N=4のケースを取り上げます。
このケースでは、4つの数字が出されるパターンに[a0,a1,a2,a3]=[2,2,1,1]のパターンがあります。
このパターンにおいて、a0,a1,a2,a3の各数字を6人が出すパターンの組み合わせは
${6}C{2} ☓ {4}C{2} ☓ {2}C{1} = 180$通りになります。
また、
a0,a1,a2,a3のそれぞれの数字を誰が出したかについては、
a0,a1,a2,a3に0..3の数字を割り当てる順列なので
${4}P{4} = 24$通りになります。
但し、「(A,B)の人が[0]を出し(C,D)の人が[1]を出した」時と、「(C,D)の人が[1]を出し(A,B)の人が[0]を出した」というのは同じで重複ですから
a0,a1に割り当てたx,yの組み合わせは、a0,a1に割り当てたy,xと同じ、つまり${2}P{2}$は重複になります。
a2,a3も同様ですから、[a0,a1,a2,a3]に割り当てられる数字の組み合わせは、$\frac{{4}P{4}}{ {2}P{2} ☓ {2}P{2} }$の6通りになります。
従って、[2,2,1,1]のケースにおける、全数字の組み合わせは、$\frac{{6}C{2} ☓ {4}C{2} ☓ {2}C{1} ☓ {4}P{4}}{ {2}P{2} ☓ {2}P{2} }=1080$通りです。
[3,1,1,1]のケースでは、a1,a2,a3ともに1で、ここが重複になります。
このパターンにおいて、a0,a1,a2,a3の各数字を6人が出すパターンの組み合わせは
${6}C{3} ☓ {3}C{1} ☓ {2}C{1} = 120$通りで
a0,a1,a2,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$通りになります。
上記の考察を踏まえて、p人がN個の数字から１つ出しあった時の、各数字の個数が[a0,a1,a2,a3]である時の、パターン数を求めるコードを作成します。
# ------------------------------------------------------------------------------------------------------------
#
# 各数字の出現回数が[a0,a1..am]となる場合の、数字の組み合わせの総数を求める
#
# ------------------------------------------------------------------------------------------------------------
#
from scipy.special import perm, comb # 順列組み合わせの計算用
class Combinations:
def __init__(self, n, terget_list):
self.n = n
self.terget_list = terget_list
def redundancy(self):
"""
重複により除去する数を算出する
Parameters
----------
Returns
-------
重複により、除するべき数
"""
current_value = 0 # 重複しているかどうかをチェックする数
counter = 0 # その数の個数
result = 1 # 結果
for i in self.terget_list:
if current_value != i:
p = perm(counter, counter) # cPc : 重複パターン数
result = result * p # 直前の重複パターン数と乗算する
counter = 1 # １個あるから
current_value = i # 次に重複をチェックすべき数
else:
counter += 1 # 同じ数が続いている
p = perm(counter, counter) # 最後の値での最後の演算
result = result * p
return result
def player_combinations(self):
"""
参加者が取りうるパターンの順列を求める
Parameters
----------
n : 値の範囲
terget_list : チェックするリスト（各数がいくつだされたかのパターン）
Returns
-------
参加者が取りうるパターンの順列数
"""
length = len(self.terget_list) # 何種類の数字が出されたか
permut = perm(self.n, length) # 全数字のうちの出された数字の順列
result = permut / self.redundancy() # 重複分を取り除く
return result
def number_combinations(self):
"""
数字の組み合わせ数を得る
Returns
-------
数字の組み合わせ数
"""
remain = sum(self.terget_list) # 参加人数を求める
result = 1 # 結果の初期値
for i in self.terget_list:
# i人が同じ数字を出す時の組み合わせ
combin = comb(remain, i)
result = result * combin # 総乗
remain = remain - i # 残りの人数
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))
勝者の数毎のパターン数を数える
期待値を求める式
$\displaystyle E_{n} = \frac{1 + \sum_{k=1}^{n-1} P(n,k)E_{k}}{(1- P(n,n))}$
において必要なのは、「勝ち残りが何人いるのかの確率」と「勝ち残った人数での期待値」ですが、「勝ち残った人数での期待値」は再帰的に求めるので
「勝ち残りが何人いるのかの確率」を計算します。
「勝ち残りが何人いるのかの確率」は、(各勝ち残り人数のパターンがいくつあるか)/(全部のパターン)なので
各勝ち残り人数毎に、パターンの総数を数えます。
各勝ち残り人数毎に、取りうる数字の組み合わせがいくつあるかを数える処理は下記の通りになります。
1) 全員が出した数字の数の組み合わせを列挙する
2) 列挙された数字のパターンが、何通りあるかを調べる
3) 列挙された数字のパターンの、勝ち残りの人数を調べる
4) 勝ち残りの人数毎に、数字のパターン総数を計算する
ここまでできれば、全てのパターンの総数で割れば確率が求まりますので、勝ち残りの人数毎の確率を得る事が出来ます
# ------------------------------------------------------------------------------------------------------------
#
# 勝ち残りの人数毎に、確率を求める
#
# ------------------------------------------------------------------------------------------------------------
#
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):
"""
勝ち残りの人数毎に、確率を求める
Parameters
----------
p : 参加人数
n : 参加者が出す数字の個数
"""
self.p = p
self.n = n
def sum_patterns_by_winner(self):
"""
勝ち残りの人数毎の組合わせパターン数を集計する
Returns
-------
list[勝者の人数] : 組合わせパターン数
"""
# 勝敗結果のリストを作る
decomp_list = DecomposingAddends().decomposing(self.p, self.n, 0)
# 参加人数分、パターン数を入れるリストを用意する(1オリジン)
self.patterns = [0] * (self.p + 1)
# 結果のリストから、勝ち残り人数毎に
for l in decomp_list:
patterns = Combinations(self.n, l).get() # 結果パターンから、それが起こるパターン数を得る
winners = count_numbers(l) # 勝ち残りの人数を得る
self.patterns[winners] += patterns
return self.patterns
def culc(self):
result = Probability.result_list[self.p, self.n]
if result is not None: # 既に計算していれば、その値を使う
return result
patterns = self.sum_patterns_by_winner()
total = self.n ** self.p
self.probability = [0.0] * (self.p) # 参加人数分、確率を入れるリストを用意する
for i in range(1, self.p):
self.probability[i] = patterns[i] / total # 確率を求める
self.probability[0] = patterns[self.p] / total # 最後の一つ（全員同じ)は、0番目に格納する
Probability.result_list[self.p, self.n] = self.probability
# 計算結果を保存しておく
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))
勝ち残り人数毎の、確率がわかったので、最後に期待値を求めます。
期待値は、既に説明した通り、下記の式によって求めます。
$\displaystyle E_{n} = \frac{1 + \sum_{k=1}^{n-1} P(n,k)E_{k}}{(1- P(n,n))}$
# ------------------------------------------------------------------------------------------------------------
#
# 期待値を求める
#
# ------------------------------------------------------------------------------------------------------------
#
#
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: # 勝ち残りが1名以下なら終了
return 0.0
elif p == 2: # 2名の時は勝負がつかないので、ジャンケンの1.5を採用
return 1.5
else:
probability = Probability(p, n).calculation() # 勝ち残りがi人になる確率のリスト
result = 1
for i in range(1, p):
probability_i = probability[i] # 勝ち残りがi人になる確率
expected_value = self.process(i, n, dummy)
expected_value = (probability_i * expected_value)
result = result + expected_value
result = result / (1 - probability[0]) # (1-全員が勝ち残こる確率)で割る
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))
まとめ
最後に整形して表にし、各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 |
# ------------------------------------------------------------------------------------------------------------
#
# N拳：p人のプレイヤーが0..(n-1)までのn個の数字を出し、出した人数が一番少なかった数字を出した人を、勝者とするゲーム
# ここでは、N拳において、p人の時、nがいくつの時が最適なのかを調べる
#
# ------------------------------------------------------------------------------------------------------------
#
from ExpectedValue import ExpectedValue
expected_value_obj = ExpectedValue() # 期待値を算出するオブジェクト
maxP = 30
text = "|p\\n|"
for n in range(2, maxP):
text = text + "{:2d}|".format(n) # 列のラベル
print(text)
text = "|-|"
for n in range(2, maxP):
text = text + "----|".format(n) # 列の横線
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)