import time
import numpy as np
N = 10
def mul(m, n):
if m > n: m, n = n, m
sum = 0
for i in range(m):
sum += n
return sum
def dev(m, n):
count = 0
while m >= n:
m -= n
count += 1
return count
def fact(n, r=1):
if n <= 1 or n <= r:
return 1
m = 1
for i in range(r, n+1):
m = mul(m, i)
return m
def show_time(func):
t_start = time.time()
for i in range(8000):
for j in range(N):
func(N, j)
t_end = time.time()
print("{0}: {1:.3f} [sec]".format(func.__name__, t_end - t_start))
def comb1(n, r):
return dev(fact(n), mul(fact(r), fact(n-r)))
def comb2(n, r):
return dev(fact(n, n-r+1), fact(r))
def comb3(n, r):
r, n = r+1, n-r+1
c = np.zeros((r, n), dtype=np.int32)
c[0], c[:] = 1, 1
for i in range(1, r):
for j in range(1, n):
c[i][j] = c[i][j-1] + c[i-1][j]
return c[r-1][n-1]
def comb4(n, r):
c = np.zeros(r+1, dtype=np.int32)
c[-1] = 1
for i in range(n): c[:r] += c[1:r+1]
return c[0]
show_time(comb1)
show_time(comb2)
show_time(comb3)
show_time(comb4)
aW1wb3J0IHRpbWUKaW1wb3J0IG51bXB5IGFzIG5wCgpOID0gMTAKCmRlZiBtdWwobSwgbik6CiAgaWYgbSA+IG46IG0sIG4gPSBuLCBtCiAgc3VtID0gMAogIGZvciBpIGluIHJhbmdlKG0pOgogICAgc3VtICs9IG4KICByZXR1cm4gc3VtCiAgCmRlZiBkZXYobSwgbik6CiAgY291bnQgPSAwCiAgd2hpbGUgbSA+PSBuOgogICAgbSAtPSBuCiAgICBjb3VudCArPSAxCiAgcmV0dXJuIGNvdW50CgpkZWYgZmFjdChuLCByPTEpOgogIGlmIG4gPD0gMSBvciBuIDw9IHI6CiAgICByZXR1cm4gMQogIG0gPSAxCiAgZm9yIGkgaW4gcmFuZ2UociwgbisxKToKICAgIG0gPSBtdWwobSwgaSkKICByZXR1cm4gbQoKZGVmIHNob3dfdGltZShmdW5jKToKICB0X3N0YXJ0ID0gdGltZS50aW1lKCkKICBmb3IgaSBpbiByYW5nZSg4MDAwKToKICAgIGZvciBqIGluIHJhbmdlKE4pOgogICAgICBmdW5jKE4sIGopCiAgdF9lbmQgPSB0aW1lLnRpbWUoKQogIHByaW50KCJ7MH06IHsxOi4zZn0gW3NlY10iLmZvcm1hdChmdW5jLl9fbmFtZV9fLCB0X2VuZCAtIHRfc3RhcnQpKQoKZGVmIGNvbWIxKG4sIHIpOgogIHJldHVybiBkZXYoZmFjdChuKSwgbXVsKGZhY3QociksIGZhY3Qobi1yKSkpCgpkZWYgY29tYjIobiwgcik6CiAgcmV0dXJuIGRldihmYWN0KG4sIG4tcisxKSwgZmFjdChyKSkKCmRlZiBjb21iMyhuLCByKToKICByLCBuID0gcisxLCBuLXIrMQogIGMgPSBucC56ZXJvcygociwgbiksIGR0eXBlPW5wLmludDMyKQogIGNbMF0sIGNbOl0gPSAxLCAxCiAgZm9yIGkgaW4gcmFuZ2UoMSwgcik6CiAgICBmb3IgaiBpbiByYW5nZSgxLCBuKToKICAgICAgY1tpXVtqXSA9IGNbaV1bai0xXSArIGNbaS0xXVtqXQogIHJldHVybiBjW3ItMV1bbi0xXQoKZGVmIGNvbWI0KG4sIHIpOgogIGMgPSBucC56ZXJvcyhyKzEsIGR0eXBlPW5wLmludDMyKQogIGNbLTFdID0gMQogIGZvciBpIGluIHJhbmdlKG4pOiBjWzpyXSArPSBjWzE6cisxXQogIHJldHVybiBjWzBdCgpzaG93X3RpbWUoY29tYjEpCnNob3dfdGltZShjb21iMikKc2hvd190aW1lKGNvbWIzKQpzaG93X3RpbWUoY29tYjQp