#!/usr/bin/python
# -*- coding: utf-8 -*-
"""Play with permutations, i.e. symmetric group elements.

Provides a convenient way to experiment with permutations in the
Python interactive REPL.

Inspired by Mark-Jason Dominus and Allen Knutson; further information
from Wikipedia.

cycle(a, b, c, d) generates a permutation that maps a to b, b to c, c
to d, and d to a, as long as they're all smallish nonnegative
integers, which is perhaps a limitation I should remove.  You can
apply the resulting object as a function or compose it with
multiplication.

>>> cycle() * cycle()
cycle()
>>> x = cycle(1, 2, 3, 4)
>>> x
cycle(1, 2, 3, 4)
>>> x(4)
1
>>> x(3)
4
>>> x * x
cycle(1, 3) * cycle(2, 4)
>>> x * x * x
cycle(1, 4, 3, 2)
>>> x * x * x * x
cycle()
>>> x * x * x * cycle(1, 2)
cycle(2, 4, 3)
>>> x * cycle(1, 2, 3)
cycle(1, 3, 2, 4)
>>> cycle(1, 2, 3) * x
cycle(1, 3, 4, 2)
>>> cycle(1, 2, 3) * cycle(1, 2, 3)
cycle(1, 3, 2)
>>> y = cycle(*range(6))
>>> y
cycle(0, 1, 2, 3, 4, 5)
>>> y * y
cycle(0, 2, 4) * cycle(1, 3, 5)
>>> y * y * y
cycle(0, 3) * cycle(1, 4) * cycle(2, 5)
>>> y * y * y * y
cycle(0, 4, 2) * cycle(1, 5, 3)
>>> y * y * y * y * y
cycle(0, 5, 4, 3, 2, 1)
>>> y ** 5
cycle(0, 5, 4, 3, 2, 1)

You can also specify the permutation directly instead of by
composing it out of cycles, although of course this is zero-based:

>>> Permutation([3, 4, 0, 1, 2, 5])
cycle(0, 3, 1, 4, 2)
>>> Permutation([0, 3, 4, 1, 2, 5])
cycle(1, 3) * cycle(2, 4)
>>> Permutation([0, 3, 4, 1, 5, 2])
cycle(1, 3) * cycle(2, 4, 5)
>>> Permutation([0, 3, 4, 1, 5, 2]) ** 2
cycle(2, 5, 4)
>>> Permutation(reversed(range(7)))
cycle(0, 6) * cycle(1, 5) * cycle(2, 4)
>>> rotate_twelve_three = range(9, 12) + range(9)
>>> rotate_twelve_three
[9, 10, 11, 0, 1, 2, 3, 4, 5, 6, 7, 8]
>>> Permutation(rotate_twelve_three)
cycle(0, 9, 6, 3) * cycle(1, 10, 7, 4) * cycle(2, 11, 8, 5)

Coercion to string produces normal mathematical cycle notation:

>>> print Permutation([0, 3, 4, 1, 5, 2])
(1 3) (2 4 5)
>>> print Permutation([0, 3, 4, 1, 5, 2]) ** 6
()
>>> print ', '.join(str((cycle(1, 2) * cycle(3, 4, 5))**ii) for ii in range(7))
(), (1 2) (3 4 5), (3 5 4), (1 2), (3 4 5), (1 2) (3 5 4), ()

As you'd expect, you can find the inverse of a permutation by taking
it to the -1 power:

>>> cycle(1, 2, 3, 4)**-1
cycle(1, 4, 3, 2)
>>> cycle(1, 2, 3, 4)**-1 * cycle(1, 2, 3, 4)
cycle()

Exponentiation is implemented reasonably efficiently so you don't have
to be scared of it:

>>> cycle(*range(12))**1000000
cycle(0, 4, 8) * cycle(1, 5, 9) * cycle(2, 6, 10) * cycle(3, 7, 11)

Permutations over large integers can be slow; this one takes about
100ms on my netbook:

>>> cycle(10000, 1)
cycle(1, 10000)

There's a `reversal` function to compute the reversal permutation for
a given range of numbers:

>>> reversal(3, 7)
cycle(3, 6) * cycle(4, 5)
>>> reversal(5, 12)
cycle(5, 11) * cycle(6, 10) * cycle(7, 9)
>>> reversal(5, 12)**2
cycle()

Permutations are hashable and comparable for equality, so you can use
them as hash keys (dubious) or store them in a set (more likely):

>>> set([cycle(), cycle(1, 2), cycle(2, 1)])
set([cycle(1, 2), cycle()])

Fun stuff to try
----------------

The structure of vector rotations is particularly interesting:

>>> for ii in range(12): print Permutation(range(ii, 12) + range(ii))
... 
()
(0 1 2 3 4 5 6 7 8 9 10 11)
(0 2 4 6 8 10) (1 3 5 7 9 11)
(0 3 6 9) (1 4 7 10) (2 5 8 11)
(0 4 8) (1 5 9) (2 6 10) (3 7 11)
(0 5 10 3 8 1 6 11 4 9 2 7)
(0 6) (1 7) (2 8) (3 9) (4 10) (5 11)
(0 7 2 9 4 11 6 1 8 3 10 5)
(0 8 4) (1 9 5) (2 10 6) (3 11 7)
(0 9 6 3) (1 10 7 4) (2 11 8 5)
(0 10 8 6 4 2) (1 11 9 7 5 3)
(0 11 10 9 8 7 6 5 4 3 2 1)

Alternatively, take the powers of the rotation by one place:

>>> for ii in range(12): print cycle(*range(12))**ii
... 
()
(0 1 2 3 4 5 6 7 8 9 10 11)
(0 2 4 6 8 10) (1 3 5 7 9 11)
(0 3 6 9) (1 4 7 10) (2 5 8 11)
(0 4 8) (1 5 9) (2 6 10) (3 7 11)
(0 5 10 3 8 1 6 11 4 9 2 7)
(0 6) (1 7) (2 8) (3 9) (4 10) (5 11)
(0 7 2 9 4 11 6 1 8 3 10 5)
(0 8 4) (1 9 5) (2 10 6) (3 11 7)
(0 9 6 3) (1 10 7 4) (2 11 8 5)
(0 10 8 6 4 2) (1 11 9 7 5 3)
(0 11 10 9 8 7 6 5 4 3 2 1)

You can see that you can compose a rotation out of three reversals,
which in practice may be a more practical way of reversing a vector in
constant space than computing and executing the cycles of the rotation
permutation:

>>> print reversal(0, 12) * reversal(0, 3) * reversal(3, 12)
(0 9 6 3) (1 10 7 4) (2 11 8 5)

You can cut a long cycle into two cycles by composing it with a
transposition:

>>> cycle(1, 2, 3, 4, 5) * cycle(2, 4)
cycle(1, 2, 5) * cycle(3, 4)
>>> cycle(*range(18)) * cycle(2, 9)
cycle(0, 1, 2, 10, 11, 12, 13, 14, 15, 16, 17) * cycle(3, 4, 5, 6, 7, 8, 9)

Bugs
----

__hash__ depends on the length of items in the internal self.items, so
it can give spurious mismatches:

>>> a = cycle(0, 1)
>>> b = cycle(2, 3)
>>> a*b*b == a
True
>>> hash(a*b*b) == hash(a)
False

"""

class Permutation:
    """A permutation, an element of a finite symmetric group.

    Representation: self.items is a tuple such that self.items[x] is
    self(x).

    """

    def __init__(self, items):
        self.items = tuple(items)
        assert set(self.items) == set(range(len(self.items)))

    def __mul__(self, other):
        "Function composition."
        return Permutation(self(other(item))
                           for item in range(max(self.end(), other.end())))

    def __eq__(self, other):
        return all(self(item) == other(item)
                   for item in range(max(self.end(), other.end())))

    def __hash__(self):
        return 1 + hash(self.items)

    def __pow__(self, power):
        """Compose a permutation with itself N times."""
        if power < 0:
            return self.inverse() ** -power
        if power == 0:
            return cycle()
        if power == 1:
            return self
        return (self * self) ** (power // 2) * self ** (power % 2)

    def __call__(self, index):
        return self.items[index] if index < len(self.items) else index

    def __repr__(self):
        "Using Python cycle notation."
        cycles = list(self.cycles())
        if not cycles:
            return 'cycle()'

        return ' * '.join('cycle(%s)' % ', '.join(map(repr, cycle))
                          for cycle in cycles)

    def __str__(self):
        "Using NORMAL cycle notation."
        cycles = list(self.cycles())
        if not cycles:
            return '()'

        return ' '.join('(%s)' % ' '.join(map(str, cycle)) for cycle in cycles)

    def cycles(self):
        """Analyze permutation into a product of disjoint cycles.

        This is very straightforward to do in linear time using Python
        set objects, but using Python set objects to find the start of
        each new cycle produces the cycles in unpredictable order.
        The algorithm here should still be linear-time (ii visits each
        index at most twice; min_leftover visits each index once; the
        initial leftovers set is produced in linear time; every other
        simple statement in the function is O(1)) and also produce the
        nonempty cycles in a deterministic order, with a deterministic
        starting point.

        """
        leftovers = set(self.items)
        min_leftover = 0

        while leftovers:
            while min_leftover not in leftovers:
                min_leftover += 1
                assert min_leftover < len(self.items)

            ii = min_leftover
            cycle = []
            cycle_set = set()
            while ii not in cycle_set:
                cycle.append(ii)
                cycle_set.add(ii)
                leftovers.remove(ii)
                ii = self(ii)

            if len(cycle) > 1:
                yield cycle

    def end(self):
        return len(self.items)

    def inverse(self):
        items = range(len(self.items))
        for index, item in enumerate(self.items):
            items[item] = index

        return Permutation(items)

def cycle(*seq):
    "Generate a permutation from a single cycle."
    items = range(max(seq or [-1])+1)
    for ii in range(len(seq)):
        items[seq[ii]] = seq[(ii+1) % len(seq)]

    return Permutation(items)

def reversal(start, end):
    return Permutation(range(start) + list(reversed(range(start, end))))

def _test():
    "Basic sanity check, performed on module import."
    a = cycle(1, 3)
    b = cycle(0, 1)
    assert a(b(1)) == (a*b)(1)

    c = cycle(1, 2)
    d = cycle(3, 4)
    assert c(d(3)) == (c*d)(3)
    assert c(d(3)) == 4
    assert d(c(3)) == (d*c)(3)
    assert d(c(3)) == 4

_test()

if __name__ == '__main__':
    print "Running doctests."
    import doctest
    doctest.testmod()