""" shuffle.py

    Perfect shuffles and shuffling machines
"""

from permutations import Permutation

def out_shuffle(n):
    """ Creates an 'out shuffle' permutation for a deck of size n """

    return Permutation(out_f(n))

def in_shuffle(n):
    """ Creates an 'in shuffle' permutation for a deck of size n """

    return Permutation(in_f(n))

def in_f(n):
    """ For n even, this takes the list [0, ... ,k, ... ,n-1]
        and replaces each k with (2*k+1) % (n+1).
    """
    if n%2 == 1:
        return in_f(n-1)+[n-1]
    else:
        f = lambda k : (2*k+1) % (n+1)
        return map(f, range(n))

def out_f(n):
    """ For n even, this takes the list [0, ... ,k, ... ,n-1]
        and replaces each k with (2*k) % (n-1).
    """
    if n%2 == 1:
        return out_f(n+1)[:n]
    else:
        inner = [k+1 for k in in_f(n-2)]
        return [0]+inner+[n-1]

def partitions(n):
    if n==1:
        return [[1]]
    else:
        LL = []
        for k in range(1,n):
            for l in partitions(n-k):
                l.append(k)
                l.sort()
                if l not in LL:
                    LL.append(l)
        LL.append([n])
        return LL

def gcd(m,n):
    if n==0:
        return abs(m)
    else:
        return gcd(n,m%n)

def lcm(m,n):
    return abs(m*n)/gcd(m,n)

def large_order(n):
    """ Finds the largest order of an element in the symmetric group on n letters. """
    p = partitions(n)
    o = [reduce(lcm,x) for x in p]
    z = zip(o,p)
    z.sort()
    return z.pop()