雑

たけしのコマ大数学科 第18回：割り当て問題 – ガスコン研究所

パッとみて，たまたま答えが28位だなあって分かってしまったので．

全部試行しても5!=120通り．ランダムに試行すれば試行数はどうなるか．

import numpy as np

a = np.array([6, 5, 6, 5, 6])
b = np.array([8, 7, 6, 8, 7])
c = np.array([4, 5, 4, 4, 5])
d = np.array([6, 7, 6, 4, 7])
e = np.array([10, 8, 10, 7, 10])
ind = np.arange(5)

for i in range(1000):
    np.random.shuffle(ind)
    if a[ind[0]] + b[ind[1]] + c[ind[2]] + d[ind[3]] + e[ind[4]] < 29:
        print(f'Task {i}')
        print(a[ind[0]] + b[ind[1]] + c[ind[2]] + d[ind[3]] + e[ind[4]])
        print(ind)
        print(a[ind[0]], b[ind[1]], c[ind[2]], d[ind[3]], e[ind[4]])
        break

Task 18
28
[4 2 0 3 1]
6 6 4 4 8

%%timeit
ind = np.arange(5)
for i in range(1000):
    np.random.shuffle(ind)
    if a[ind[0]] + b[ind[1]] + c[ind[2]] + d[ind[3]] + e[ind[4]] < 29:
        #print(f'Task {i}')
        #print(a[ind[0]] + b[ind[1]] + c[ind[2]] + d[ind[3]] + e[ind[4]])
        #print(ind)
        #print(a[ind[0]], b[ind[1]], c[ind[2]], d[ind[3]], e[ind[4]])
        break

2.1 ms ± 232 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

1万回試して，試行数のボックスプロットをみる．

%matplotlib inline
import matplotlib.pyplot as plt
import seaborn as sns
import numpy as np


a = np.array([6, 5, 6, 5, 6])
b = np.array([8, 7, 6, 8, 7])
c = np.array([4, 5, 4, 4, 5])
d = np.array([6, 7, 6, 4, 7])
e = np.array([10, 8, 10, 7, 10])
ind = np.arange(5)

res = []
for _ in range(10000):
    for i in range(1000):
        np.random.shuffle(ind)
        if a[ind[0]] + b[ind[1]] + c[ind[2]] + d[ind[3]] + e[ind[4]] < 29:
            res.append(i)
            break

sns.boxplot(x=res)

下限は0，上限は899回，およそ全試行数が期待される．

numpy使っているけど，numpy使っていないので，
（最初はちょっとテクニカルな事を考えていた……こんがらがって時間掛かりすぎたので断念）

この場合はnumpy使わない方が勿論速い．

import random

a = [6, 5, 6, 5, 6]
b = [8, 7, 6, 8, 7]
c = [4, 5, 4, 4, 5]
d = [6, 7, 6, 4, 7]
e = [10, 8, 10, 7, 10]
ind = list(range(5))

for i in range(1000):
    random.shuffle(ind)
    if a[ind[0]] + b[ind[1]] + c[ind[2]] + d[ind[3]] + e[ind[4]] < 29:
        print(f'Task {i}')
        print(a[ind[0]] + b[ind[1]] + c[ind[2]] + d[ind[3]] + e[ind[4]])
        print(ind)
        print(a[ind[0]], b[ind[1]], c[ind[2]], d[ind[3]], e[ind[4]])
        break

Task 99
28
[4, 2, 0, 3, 1]
6 6 4 4 8

%%timeit
ind = list(range(5))

for i in range(1000):
    random.shuffle(ind)
    if a[ind[0]] + b[ind[1]] + c[ind[2]] + d[ind[3]] + e[ind[4]] < 29:
        #print(f'Task {i}')
        #print(a[ind[0]] + b[ind[1]] + c[ind[2]] + d[ind[3]] + e[ind[4]])
        #print(ind)
        #print(a[ind[0]], b[ind[1]], c[ind[2]], d[ind[3]], e[ind[4]])
        break

1.06 ms ± 51.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

factorial(10) = 3628800

位なら，正直ランダムに総当りしても30秒位で解けるし（最悪でも3分程度），
（上のは線形時間だけど，numpy使って並列化すればもっと速くなる）
（後，ちゃんと調べていないので，また後日はっきりさせたいけど，）
（ループ処理の場合はnumpy駄目絶対，ピュアに書こうが常識だと思っていたけど，）
（ループ回数が1000，10,000回を超える様な処理の場合には，numpyの方が速いかも）
（ピュアな書き方は安定して線形時間なのに対して，numpyはほぼ線形時間だけど20％位速くなる）

factorial(100) = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

とかになってくると，何かしらの法則，制約条件が無ければどの様な方法でも解けないだろうし，
むしろヒューリスティックな方法が必要になってくるんだろう．