perm_no_fix.py

""" Computing the number of permutations on n points 
no fix points in 3 ways. """
from functools import wraps
from math import factorial, e, floor
from sys import argv

CACHE = {}

def cache(f):
    @wraps(f)
    def cached(*args, **kwargs):
        key = "%s - %s - %s - %s" % (
            f.__module__,
            f.__name__,
            str(args),
            str(kwargs))
        global CACHE
        if key not in CACHE:
            CACHE[key] = f(*args, **kwargs)
        return CACHE[key]
    return cached

@cache
def comb(a, b):
    assert a >= b
    return factorial(a) / factorial(b) / factorial(a - b)


@cache
def s(n):
    """ This is the recursive way. The idea is we group
    on the cycle length the first element is in. It can
    be anything but 1 and n - 1. If the cycle length(c)
    is not n then the rest of the elements can be s(n - c)
    ways. """
    if n < 4:
        return [0,1,2][n - 1]
    ret = factorial(n - 1)
    for i in xrange(2, n - 2 + 1):
        ret += comb(n - 1, i - 1) * factorial(i - 1) * s(n - i)
    return ret

def s2(n):
    """ This is a somewhat more direct formula which can be
    derived using the sieve method. """
    acc = 0
    for i in xrange(n + 1):
        multi = -1 if i % 2 == 1 else 1
        acc += multi * (factorial(n) / factorial(i))
    return acc

def s3(n):
    """ This is an explicit formula which can be derived from
    the s2 version. """
    return int(floor(factorial(n) / e + 1 / 2.))


if __name__ == "__main__":
    total = int(argv[1])
    for i in xrange(1, total + 1):
        print i, s(i), s2(i), s3(i)