# permutations.py

from types import IntType,ListType,TupleType
import random
from string import ascii_lowercase as LOWER
from string import ascii_uppercase as UPPER

class Permutation(object):
    """ Stores a permutation in two forms: as a list P where
        the convention is that if P[i]=j then P takes i to j,
        and as a list C of disjoint 'cycles'.

        Note: permutations act on the left by default!
    """

    def __init__(self,perm,length=0,onLeft=True):
        """ The input 'perm' can be a list/tuple of integers, a
            list/tuple of characters, a string, a list/tuple of
            lists/tuples of integers or characters. Characters
            are converted to integers by 'a'->0, 'b'->1, etc.
            Integers are converted to characters for printing if
            the 'length' of the permutation is no more than 26.

            Some examples follow of what various inputs accomplish.

            If the input is (2,0,1) the resulting permutation takes
            0 to 2, 1 to 0, and 2 to 1. Similarly if the input had
            been ('c','a','b') or 'cab'.

            On the other hand, an input of ((2,0,1)) represents the
            3-cycle that takes 0 to 1, 1 to 2, and 2 to 0. Similarly
            for the input (('c','a','b')).

            The permutation representation - as in the first type of
            input - is stored in self.P, and the cycle representation -
            as in the second type of input - is stored in self.C.
        """

        # First handle the case where the input is in cycle notation.
        if type(perm[0]) in (ListType,TupleType):

            # A cycle can be given as a string or as a list/tuple of
            # integers/characters. Convert all cycles to lists of integers.
            cycles = [map(char2int,cycle) for cycle in perm]

            # Now convert this to the standard permutation form of a
            # tuple of integers.
            perm = permForm(cycles,length=length,onLeft=onLeft)

        # Next handle the case where the input is in permutation notation.
        else:

            # Permutations can be given as strings or as lists/tuples of
            # integers/characters. Convert any of these to a list of integers.
            perm = map(char2int,perm)

        self.P = perm
        self.C = cycleForm(perm)
        self.onLeft = onLeft

    def __repr__(self):
        return self.asCycles()

    def __str__(self):
        return self.asPermutation()

    def asPermutation(self):
        """ Trys to convert the permutation form to letters,
            displaying the plaintext (lowercase) above the
            ciphertext (uppercase). If the permutation is
            too long to be represented by letters, then the
            tuple self.P is displayed.
        """
        N = len(self)
        if N <= 26:
            pt = " ".join(list(LOWER)[:N])
            CT = " ".join(map(int2char,self.P)).upper()
            return pt+"\n"+CT
        else:
            return str(self.P)

    def asCycles(self):
        """ Trys to convert the cycle form to letters, displaying
            each cycle in a space delimited format. The cycles are
            then shown in a tuple. If the permutation is too long
            to be represented by letters, then the tuple of cycles
            self.C is displayed.
        """
        if len(self) <= 26:
            cycles = map(cycleString,self.C)
            return '(' + ",".join(cycles) + ')'
        else:
            return str(self.C)

    def copy(self):
        L = list(self.P[:])
        return Permutation(L)

    def __mul__(left,right):
        """ left * right
        """

        return Permutation(left.C + right.C,onLeft=left.onLeft)

    def __invert__(self):
        """ ~self returns the inverse.
        """
        # Reverse input and output of permutation.
        PL = [(k,i) for (i,k) in enumerate(self.P)]

        # Sort by output instead of input.
        PL.sort()

        # Extract inputs now ordered by outputs.
        PL = [i for (k,i) in PL]

        return Permutation(PL)

    def __div__(left,right):
        """ left / right returns the left times the
            inverse of the right.
        """
        return left * (~right)

    def __pow__(base,expo):
        """ base ** expo """
        # Negative exponents are OK too.
        if expo < 0:
            return (~base)**(-expo)

        a=Permutation(range(len(base)))
        b=base.copy()
        e=expo
        while e>0:
            q,r=divmod(e,2)
            if r==1:
                a*=b
            b*=b
            e=q
        return a

    def __eq__(left,right):
        """ left == right """
        try:
            return left.P == right.P
        except:
            return False

    def __ne__(left,right):
        """ right != left """
        return not left==right

    def __lshift__(base,exp):
        """ x<<y -> i(y)*x*y
            i.e. right action of y on x
            via conjugation.
        """

        # Adjust if permutations act on the left.
        if base.onLeft: exp = ~exp

        # Construct permutation of conjugate.
        CL = action(base,exp)

        return Permutation(CL,length=len(base),onLeft=base.onLeft)

    def __rshift__(exp,base):
        """ x>>y -> x*y*i(x)
            i.e. left action of exp on base
            via conjugation.
        """

        # Adjust if permutations act on the right.
        if not base.onLeft: exp = ~exp

        # Construct permutation of conjugate.
        CL = action(base,exp)

        return Permutation(CL,length=len(base),onLeft=base.onLeft)

    def __len__(self):
        return len(self.P)

    def encipher(self,c):
        try:
            c = UPPER.index(c.upper())
            c = UPPER[self.P[c]]
        except:
            pass

        return c

    def decipher(self,c):
        try:
            c = UPPER.index(c.upper())
            c = UPPER[self.P.index(c)]
        except:
            pass

        return c

    def cycleStructure(self):
        structure =  map(len,self.C)
        structure.sort()
        return structure

    def fixedPoints(self):
        FP = set([i for (i,k) in enumerate(self.P) if i==k])
        return FP

def cycleForm(P):
    """ The input must be a permutation of range(n) for some n.
    """

    # Construct the list of (supposed) permuted integers.
    L = range(len(P))

    # Check that P is, in fact, a permutation of L.
    assert set(L)==set(P)

    # We'll store the list of cycles in 'CL'.
    CL = []
    while L:
        # If we're not working on a cycle, pop an entry
        # off the list 'L' for the start of the next cycle.
        x = L.pop(0)
        cycle = [x]

        while 1:
            # Look for the next item in the current cycle,
            # remove the item from 'L' and add it to the cycle.
            # But, if we're back at the start, close the cycle.

            try:
                y = P[x]
                L.remove(y)
                cycle.append(y)
                x = y
            except ValueError:
                CL.append(cycle)
                break

    # Order the cycles by length, shortest first.
    CL = [(len(c),c) for c in CL]
    CL.sort()
    CL = [c for (l,c) in CL]

    return CL

def permForm(CL,length=0,onLeft=True):
    n = max(1 + max(map(max,CL)),length)
    # In case CL involves tuples instead of lists:
    CL = [list(c) for c in CL]
    if onLeft:
        CL.reverse()
    L = range(n)
    for k in L:
        x = k
        for c in CL:
            try:
                x = c[1+c.index(x)]
            except IndexError:
                x = c[0]
            except ValueError:
                pass
        L[k] = x

    return L

def char2int(c):
    try:    return LOWER.index(c.lower())
    except: return c

def int2char(k):
    try:    return LOWER[k]
    except: return k

def cycleString(cycle):
    cycle = map(int2char,cycle)
    strng = '('+" ".join(cycle)+')'
    return strng

def bugger(na):
    print "\n------ bugger ------"
    for x in na:
        try:
            print x
        except:
            pass

def action(base,exp):
    """ Takes the cycle structure of base
        and applies exp to each element.
        This is the right (left) action of exp
        on base if perms act on the right (left).
    """
    def encipher(k):
        try: return exp.P[k]
        except: return k

    CL = [map(encipher,c) for c in base.C]
    return CL

def lencmp(x,y):
    lx,ly = len(x),len(y)
    if lx<ly:   return -1
    elif lx>ly: return  1
    else:
        if x[0]<y[0]:   return -1
        elif x[0]>y[0]: return  1
        else:           return  0

if __name__ == "__main__":

    clist = ((0,1),(2,3))
    print permForm(((0,1),(2,3)))
    print Permutation(clist)
    print Permutation([3,2,4,0,1])


    """
    n = 6

    I=Permutation(range(n))

    T=range(n)
    T.reverse()
    T=Permutation(T)

    SL = [T]
    for k in range(10):
        X=range(n)
        random.shuffle(X)
        X=Permutation(X)
        NP = X*T/X
        if NP not in SL:
            SL.append(X*T/X)

    for i,P in enumerate(SL):
        print i,P

    print

    for i,P in enumerate(SL):
        for j,Q in enumerate(SL):
            if P != Q:
                print i,j,P*Q

    """