# derange.py
# count derangements
# Time the different versions of derangement counter

import math, timeit
import matplotlib.pyplot as plt

NUM_ITERS = 1000


def timer(fn, iters):
  t = timeit.timeit(fn+"(n)", globals=globals(), number=iters)
  return t


def countDer(n):
  if n == 0: 
    return 1
  elif n == 1: 
    return 0
  else:
    return (n-1) * \
       (countDer(n-1) + countDer(n-2))


def countDer2(n):
  if n == 0: 
    return 1
  else:
    return n*countDer2(n-1) + (-1)**n


def countDerIter(n):
  if n == 0: 
    return 1
  elif n == 1: 
    return 0
  prev = 0
  dr = 1
  for i in range(3, n+1): 
    curr = (i-1)*(prev+dr)
    prev = dr
    dr = curr
  return dr 


def countDerIter2(n):
  if n == 0: 
    return 1
  mult = -1
  dr = 1
  for i in range(1, n+1): 
    dr = i*dr + mult
    mult *= -1
  return dr 


def countDerApprox(n):
  return int(math.factorial(n)/math.e + 0.5)


if __name__ == "__main__":
  ns = [] 
  d = []; d2 = []
  di = []; di2 = []
  da = []
  for n in range(8, 30):
    ns.append(n)
    # d.append( timer('countDer', NUM_ITERS))
    d2.append( timer('countDer2', NUM_ITERS))
    di.append( timer('countDerIter', NUM_ITERS))
    di2.append( timer('countDerIter2', NUM_ITERS))
    da.append( timer('countDerApprox', NUM_ITERS))
  
  # plt.plot(ns, d, label="recursive")
  plt.plot(ns, d2, label="recursive 2", ls='-.')
  plt.plot(ns, di, label="iterative",lw=3)
  plt.plot(ns, di2, label="iterative 2", ls='--')
  plt.plot(ns, da, label="Approx")
  
  plt.legend()
  plt.xlabel("n")
  plt.ylabel("Secs")
  plt.title('Times for D_n')
  
  plt.show()