<commit_before>import bisect
import collections
import itertools
import math
import numbers
import operator
import random

from .interfaces.flippable import Flippable
from .interfaces.patt import Patt
from .interfaces.rotatable import Rotatable
from .interfaces.shiftable import Shiftable
from .misc.iterable_floor_and_ceiling import left_floor_and_ceiling

__all__ = ("Perm",)


class Perm(tuple, Patt, Rotatable, Shiftable, Flippable):
    """A perm class."""

    _TYPE_ERROR = "'{}' object is not a perm"

    #
    # Methods returning a single Perm instance
    #

    def __new__(cls, iterable=(), check=False):
        """Return a Perm instance.

        Args:
            cls:
                The class of which an instance is requested.
            iterable: <collections.Iterable> or <numbers.Integral>
                An iterable corresponding to a legal perm.
                Also supports passing just a number with unique digits.

        Raises:
            TypeError:
                Bad argument type.
            ValueError:
                Bad argument, but correct type.

        Examples:
            >>> Perm((0, 3, 1, 2))
            Perm((0, 3, 1, 2))
            >>> Perm(range(5, -1, -1))
            Perm((5, 4, 3, 2, 1, 0))
            >>> Perm("abc", check=True)  # Not good
            Traceback (most recent call last):
                ...
            TypeError: ''a'' object is not an integer
        """
        return tuple.__new__(cls, iterable)

    def __init__(self, iterable=(), check=False):
        # Cache for data used when finding occurrences of self in a perm
        self._cached_pattern_details = None
        if check:
            self._init_checked()

    def _init_checked(self):
        """Checks if a suitable iterable given when initialised."""
        used = [False] * len(self)
        for value in self:
            if not isinstance(value, numbers.Integral):
                message = "'{}' object is not an integer".format(repr(value))
                raise TypeError(message)
            if not 0 <= value < len(self):
                raise ValueError("Element out of range: {}".format(value))
            if used[value]:
                raise ValueError("Duplicate element: {}".format(value))
            used[value] = True

    _to_standard_cache = {}

    @classmethod
    def to_standard(cls, iterable):
        """Return the perm corresponding to iterable.

        Duplicate elements are allowed and become consecutive elements (see
        example).

        The standardize alias is supplied for backwards compatibility with
        permpy.  However, the permpy version did not allow for duplicate
        elements.

        Examples:
            >>> Perm.to_standard("a2gsv3")
            Perm((2, 0, 3, 4, 5, 1))
            >>> Perm.to_standard("caaba")
            Perm((4, 0, 1, 3, 2))
        """
        # TODO: Do performance testing
        iterable = tuple(iterable)
        if iterable not in Perm._to_standard_cache:
            result = [None] * len(iterable)
            value = 0
            for (index, _) in sorted(enumerate(iterable), key=operator.itemgetter(1)):
                result[index] = value
                value += 1
            Perm._to_standard_cache[iterable] = cls(result)
        return Perm._to_standard_cache[iterable]

    standardize = to_standard  # permpy backwards compatibility
    from_iterable = to_standard

    @classmethod
    def from_integer(cls, integer):
        """Return the perm corresponding to the integer given. The permutation
        can be given one-based or zero-base but it will be returned in 0-based.

        Examples:
            >>> Perm.from_integer(123)
            Perm((0, 1, 2))
            >>> Perm.from_integer(321)
            Perm((2, 1, 0))
            >>> Perm.from_integer(201)
            Perm((2, 0, 1))
        """
        if isinstance(integer, numbers.Integral):
            if not 0 <= integer <= 9876543210:
                raise ValueError("Illegal perm: {}".format(integer))
            digit_list = []
            if integer == 0:
                digit_list.append(integer)
            else:
                while integer != 0:
                    digit_list.append(integer % 10)
                    integer //= 10
                digit_list.reverse()
            return Perm.to_standard(digit_list)
        else:
            raise TypeError("{} is not an integer".format(repr(integer)))

    @classmethod
    def from_string(cls, string, check=False):
        """Return the perm corresponding to the string given.

        Examples:
            >>> Perm.from_string("203451")
            Perm((2, 0, 3, 4, 5, 1))
            >>> Perm.from_string("40132")
            Perm((4, 0, 1, 3, 2))
        """
        if isinstance(string, str):
            if string == "ε":
                return cls([], check=check)
            else:
                return cls(map(int, string), check=check)
        # TODO: throw exception when not a string

    @classmethod
    def one_based(cls, iterable):
        """A way to enter a perm in the traditional permuta way.

        Examples:
            >>> Perm.one_based((4, 1, 3, 2))
            Perm((3, 0, 2, 1))
        """
        return cls((element - 1 for element in iterable))

    one = one_based
    proper = one_based
    scientific = one_based

    @classmethod
    def identity(cls, length):
        """Return the identity perm of the specified length.

        Examples:
            >>> Perm.identity(0)
            Perm(())
            >>> Perm.identity(4)
            Perm((0, 1, 2, 3))
        """
        return cls(range(length))

    @classmethod
    def random(cls, length):
        """Return a random perm of the specified length.

        Examples:
            >>> perm = Perm.random(8)
            >>> len(perm) == 8
            True
            >>> # TODO: test perm in PermSet(8)
        """
        result = list(range(length))
        random.shuffle(result)
        return cls(result)

    @classmethod
    def monotone_increasing(cls, length):
        """Return a monotone increasing perm of the specified length.

        Examples:
            >>> Perm.monotone_increasing(0)
            Perm(())
            >>> Perm.monotone_increasing(4)
            Perm((0, 1, 2, 3))
        """
        return cls(range(length))

    @classmethod
    def monotone_decreasing(cls, length):
        """Return a monotone decreasing perm of the specified length.

        Examples:
            >>> Perm.monotone_decreasing(0)
            Perm(())
            >>> Perm.monotone_decreasing(4)
            Perm((3, 2, 1, 0))
        """
        return cls(range(length - 1, -1, -1))

    @classmethod
    def unrank(cls, number, length=None):
        """

        Examples:
            >>> Perm.unrank(0)
            Perm(())
            >>> Perm.unrank(1)
            Perm((0,))
            >>> Perm.unrank(2)
            Perm((0, 1))
            >>> Perm.unrank(3)
            Perm((1, 0))
            >>> Perm.unrank(4)
            Perm((0, 1, 2))
            >>> Perm.unrank(5)
            Perm((0, 2, 1))
            >>> Perm.unrank(1, 3)
            Perm((0, 2, 1))
        """
        # TODO: Docstring, and do better? Assertions and messages
        #       Implement readably, nicely, and efficiently
        if length is None:
            # Work out the length and number from the number given
            assert isinstance(number, numbers.Integral)
            assert number >= 0
            if number == 0:
                return cls()
            length = 1
            amount = 1  # Amount of perms of length
            while number > amount:
                number -= amount
                length += 1
                amount *= length
            number -= 1
        else:
            assert isinstance(length, numbers.Integral)
            assert length >= 0
            assert 0 <= number < math.factorial(length)
        return cls(Perm.__unrank(number, length))

    @staticmethod
    def __unrank(number, length):
        candidates = list(range(length))
        for value in range(1, length + 1):
            factorial = math.factorial(length - value)
            division = number // factorial
            yield candidates.pop(division)
            number %= factorial

    ind2perm = unrank  # permpy backwards compatibility

    #
    # Methods modifying/combining Perm instances
    #

    def direct_sum(self, *others):
        """Return the direct sum of two or more perms.

        Args:
            self:
                A perm.
            others: <permuta.Perm> argument list
                Perms.

        Returns: <permuta.Perm>
            The direct sum of all the perms.

        Examples:
            >>> Perm((0,)).direct_sum(Perm((1, 0)))
            Perm((0, 2, 1))
            >>> Perm((0,)).direct_sum(Perm((1, 0)), Perm((2, 1, 0)))
            Perm((0, 2, 1, 5, 4, 3))
        """
        result = list(self)
        shift = len(self)
        for other in others:
            if not isinstance(other, Perm):
                raise TypeError(Perm._TYPE_ERROR.format(repr(other)))
            result.extend(element + shift for element in other)
            shift += len(other)
        return Perm(result)

    def skew_sum(self, *others):
        """Return the skew sum of two or more perms.

        Args:
            self:
                A perm.
            others: <permuta.Perm> argument list
                Perms.

        Returns: <permuta.Perm>
            The skew sum of all the perms.

        Examples:
            >>> Perm((0,)).skew_sum(Perm((0, 1)))
            Perm((2, 0, 1))
            >>> Perm((0,)).skew_sum(Perm((0, 1)), Perm((2, 1, 0)))
            Perm((5, 3, 4, 2, 1, 0))
        """
        shift = sum(len(other) for other in others)
        result = [element + shift for element in self]
        for index in range(len(others)):
            other = others[index]
            if not isinstance(other, Perm):
                raise TypeError(Perm._TYPE_ERROR.format(repr(other)))
            shift -= len(other)
            result.extend(element + shift for element in other)
        return Perm(result)

    def compose(self, *others):
        """Return the composition of two or more perms.

        Args:
            self:
                A perm.
            others: <permuta.Perm> argument list
                Perms.

        Returns: <permuta.Perm>
            The consecutive pointwise application of all the above perms
            in reverse order.

        Raises:
            TypeError:
                An object in the argument list is not a perm.
            ValueError:
                A perm in the argument list is of the wrong length.

        Examples:
            >>> Perm((0, 3, 1, 2)).compose(Perm((2, 1, 0, 3)))
            Perm((1, 3, 0, 2))
            >>> Perm((1, 0, 2)).compose(Perm((0, 1, 2)), Perm((2, 1, 0)))
            Perm((2, 0, 1))
        """
        for other in others:
            if not isinstance(other, Perm):
                raise TypeError(Perm._TYPE_ERROR.format(repr(other)))
            if len(other) != len(self):
                raise ValueError("Perm length mismatch")
        result = [None] * len(self)
        for value in range(len(self)):
            composed_value = value
            for other in reversed(others):
                composed_value = other[composed_value]
            composed_value = self[composed_value]
            result[value] = composed_value
        return Perm(result)

    multiply = compose

    def insert(self, index=None, new_element=None):
        """Return the perm acquired by adding a new element.

        Args:
            index: <int>
                Where in the perm the value is to occur.
                If None, the value defaults to len(self)+1.
            new_element: <int>
                An integer in the range of 0 to len(self) inclusive.
                If None, the element defaults to len(self).

        Returns: <permuta.Perm>
            The perm with the added element (and other elements adjusted
            as needed).

        Raises:
            IndexError:
                Index is not valid.
            ValueError:
                Element passed cannot legally be added to perm.
            TypeError:
                Element passed is not an integer.

        Examples:
            >>> Perm((0, 1)).insert()
            Perm((0, 1, 2))
            >>> Perm((0, 1)).insert(0)
            Perm((2, 0, 1))
            >>> Perm((2, 0, 1)).insert(2, 1)
            Perm((3, 0, 1, 2))
        """
        if index is None:
            index = len(self) + 1
        if new_element is None:
            new_element = len(self)
        else:
            if not isinstance(new_element, numbers.Integral):
                raise TypeError(
                    "'{}' object is not an integer".format(repr(new_element))
                )
            if not 0 <= new_element <= len(self):
                raise ValueError("Element out of range: {}".format(new_element))
        slice_1 = (
            element if element < new_element else element + 1
            for element in itertools.islice(self, index)
        )
        slice_2 = (
            element if element < new_element else element + 1
            for element in itertools.islice(self, index, len(self))
        )
        return Perm(itertools.chain(slice_1, (new_element,), slice_2))

    def remove(self, index=None):
        """Return the perm acquired by removing an element at a specified index.

        Args:
            index: <int>
                The index of the element to be removed.
                If None, the greatest element of the perm is removed.

        Returns: <permuta.Perm>
            The perm without the element (and other elements adjusted).

        Raises:
            IndexError:
                Index is not valid.

        Examples:
            >>> Perm((2, 0, 1)).remove()
            Perm((0, 1))
            >>> Perm((3, 0, 1, 2)).remove(0)
            Perm((0, 1, 2))
            >>> Perm((2, 0, 1)).remove(2)
            Perm((1, 0))
            >>> Perm((0,)).remove(0)
            Perm(())
        """
        if index is None:
            return self.remove_element()
        selected = self[index]
        return Perm(
            element if element < selected else element - 1
            for element in self
            if element != selected
        )

    def remove_element(self, selected=None):
        """Return the perm acquired by removing a specific element from self.

        Args:
            selected: <int>
                The element selected to be removed. It is an integer in the
                range of 0 to len(self) inclusive. If None, it defaults to
                len(self) - 1.

        Returns: <permuta.Perm>
            The perm with the selected element removed (and other
            elements adjusted as needed).

        Raises:
            ValueError:
                Selected element does not belong to perm.
            TypeError:
                Element passed is not an integer.

        Examples:
            >>> Perm((3, 0, 1, 2)).remove_element()
            Perm((0, 1, 2))
            >>> Perm((3, 0, 2, 1)).remove_element(0)
            Perm((2, 1, 0))
        """
        if selected is None:
            selected = len(self) - 1
        else:
            if not isinstance(selected, numbers.Integral):
                raise TypeError("'{}' object is not an integer".format(repr(selected)))
            if not 0 <= selected < len(self):
                raise ValueError("Element out of range: {}".format(selected))
        return Perm(
            element if element < selected else element - 1
            for element in self
            if element != selected
        )

    def inflate(self, components):
        """Inflate elements of the permutation to create a new one.

        Args:
            component: <collections.Iterable> of <permuta.Perm>
                This can also be a dict with keys and perms...

        Returns: <permuta.Perm>

        Examples:
            >>> Perm((0, 1)).inflate([Perm((1, 0)), Perm((2, 1, 0))])
            Perm((1, 0, 4, 3, 2))
            >>> Perm((1, 0, 2)).inflate([None, Perm((0, 1)), Perm((0, 1))])
            Perm((2, 0, 1, 3, 4))
            >>> Perm((0, 2, 1)).inflate({2: Perm((0, 1, 2))})
            Traceback (most recent call last):
                ...
            NotImplementedError
            >>> # Can also deflate points
            >>> Perm((0, 1)).inflate([Perm(), Perm()])
            Perm(())
        """
        # TODO: Spitshine method and docstring
        if isinstance(components, collections.abc.Mapping):
            raise NotImplementedError
        elif isinstance(components, collections.abc.Iterable):
            components = tuple(components)
            assert len(components) == len(self)
            shift = 0
            shifts = [0] * len(self)
            for index in self.inverse():
                shifts[index] = shift
                component = components[index]
                shift += 1 if component is None else len(component)
            perm_elements = []
            for index, component in enumerate(components):
                if component is None:
                    perm_elements.append(shifts[index])
                else:
                    shift = shifts[index]
                    perm_elements.extend(element + shift for element in component)
            return Perm(perm_elements)
        else:
            raise TypeError

    def contract_inc_bonds(self):
        # TODO: test
        monblocks = self.monotone_block_decompositon_ascending(with_ones=True)
        return Perm.to_standard([start for (start, end) in monblocks])

    def contract_dec_bonds(self):
        # TODO: test
        monblocks = self.monotone_block_decompositon_descending(with_ones=True)
        return Perm.to_standard([start for (start, end) in monblocks])

    def contract_bonds(self):
        # TODO: reimplement by calling contract_{inc,dec}_bonds or remove
        pass

    #
    # Methods for basic Perm transforming
    #

    def inverse(self):
        """Return the inverse of the perm self.

        Examples:
            >>> Perm((1, 2, 5, 0, 3, 4)).inverse()
            Perm((3, 0, 1, 4, 5, 2))
            >>> Perm((2, 0, 1)).inverse().inverse() == Perm((2, 0, 1))
            True
            >>> Perm((0, 1)).inverse()
            Perm((0, 1))
        """
        len_perm = len(self)
        result = [None] * len_perm
        for index in range(len_perm):
            result[self[index]] = index
        return Perm(result)

    def reverse(self):
        """Return the reverse of the perm self.

        Examples:
            >>> Perm((1, 2, 5, 0, 3, 4)).reverse()
            Perm((4, 3, 0, 5, 2, 1))
            >>> Perm((0, 1)).reverse()
            Perm((1, 0))
        """
        return Perm(self[::-1])

    def complement(self):
        """Return the complement of the perm self.

        Examples:
            >>> Perm((1, 2, 3, 0, 4)).complement()
            Perm((3, 2, 1, 4, 0))
            >>> Perm((2, 0, 1)).complement()
            Perm((0, 2, 1))
        """
        base = len(self) - 1
        return Perm(base - element for element in self)

    def reverse_complement(self):
        """Return the reverse complement of self.

        Equivalent to two left or right rotations.

        Examples:
            >>> Perm((1, 2, 3, 0, 4)).reverse_complement()
            Perm((0, 4, 1, 2, 3))
            >>> Perm((2, 0, 1)).reverse_complement()
            Perm((1, 2, 0))
        """
        base = len(self) - 1
        return Perm(base - element for element in reversed(self))

    def shift_right(self, times=1):
        """Return self shifted times steps to the right.

        If shift is negative, shifted to the left.

        Examples:
            >>> Perm((0, 1, 2)).shift_right()
            Perm((2, 0, 1))
            >>> Perm((0, 1, 2)).shift_right(-4)
            Perm((1, 2, 0))
        """
        if len(self) == 0:
            return self
        times = times % len(self)
        if times == 0:
            return self
        index = len(self) - times
        slice_1 = itertools.islice(self, index)
        slice_2 = itertools.islice(self, index, len(self))
        return Perm(itertools.chain(slice_2, slice_1))

    def shift_left(self, times=1):
        """Return self shifted times steps to the left.

        If shift is negative, shifted to the right.

        Examples:
            >>> Perm((0, 1, 2)).shift_left()
            Perm((1, 2, 0))
            >>> Perm((0, 1, 2)).shift_left(-4)
            Perm((2, 0, 1))
        """
        return self.shift_right(-times)

    shift = shift_right
    cyclic_shift = shift_right
    cyclic_shift_right = shift_right
    cyclic_shift_left = shift_left

    def shift_up(self, times=1):
        """Return self shifted times steps up.

        If times is negative, shifted down.

        Examples:
            >>> Perm((0, 1, 2, 3)).shift_up(1)
            Perm((1, 2, 3, 0))
            >>> Perm((0, 1, 2, 3)).shift_up(-7)
            Perm((1, 2, 3, 0))
            >>> Perm((0,)).shift_up(1234)
            Perm((0,))
        """
        if len(self) == 0:
            return self
        times = times % len(self)
        if times == 0:
            return self
        bound = len(self)
        return Perm((element + times) % bound for element in self)

    def shift_down(self, times=1):
        """Return self shifted times steps down.

        If times is negative, shifted up.

        Examples:
            >>> Perm((0, 1, 2, 3)).shift_down(1)
            Perm((3, 0, 1, 2))
            >>> Perm((0, 1, 2, 3)).shift_down(-7)
            Perm((3, 0, 1, 2))
            >>> Perm((0,)).shift_down(1234)
            Perm((0,))
        """
        return self.shift_up(-times)

    def flip_horizontal(self):
        """Return self flipped horizontally.

        Examples:
            >>> Perm((1, 2, 3, 0, 4)).flip_horizontal()
            Perm((3, 2, 1, 4, 0))
            >>> Perm((2, 0, 1)).flip_horizontal()
            Perm((0, 2, 1))
        """
        return self.complement()

    def flip_vertical(self):
        """Return self flipped vertically.

        Examples:
            >>> Perm((1, 2, 5, 0, 3, 4)).flip_vertical()
            Perm((4, 3, 0, 5, 2, 1))
            >>> Perm((0, 1)).flip_vertical()
            Perm((1, 0))
        """
        return self.reverse()

    def flip_diagonal(self):
        """Return self flipped along the diagonal.

        Examples:
            >>> Perm((1, 2, 5, 0, 3, 4)).flip_diagonal()
            Perm((3, 0, 1, 4, 5, 2))
            >>> Perm((0, 1)).flip_diagonal()
            Perm((0, 1))
        """
        return self.inverse()

    def flip_antidiagonal(self):
        """Return self flipped along the antidiagonal..

        Examples:
            >>> Perm((3, 2, 0, 1)).flip_antidiagonal()
            Perm((3, 2, 0, 1))
            >>> Perm((1, 2, 3, 0, 4)).flip_antidiagonal()
            Perm((0, 2, 3, 4, 1))
            >>> Perm((1, 2, 0, 3)).flip_antidiagonal()
            Perm((0, 2, 3, 1))
        """
        len_perm = len(self)
        result = [None] * len_perm

        flipped_pairs = (
            (len_perm - element - 1, len_perm - index - 1)
            for index, element in enumerate(self)
        )

        for index, element in flipped_pairs:
            result[index] = element
        return Perm(result)

    def _rotate_right(self):
        """Return self rotated 90 degrees to the right."""
        len_perm = len(self)
        result = [None] * len_perm
        for index, value in enumerate(self):
            result[value] = len_perm - index - 1
        return Perm(result)

    def _rotate_left(self):
        """Return self rotated 90 degrees to the left."""
        len_perm = len(self)
        result = [None] * len_perm
        for index, value in enumerate(self):
            result[len_perm - value - 1] = index
        return Perm(result)

    def _rotate_180(self):
        """Return self rotated 180 degrees."""
        return self.reverse_complement()

    def all_syms(self):
        """Returns all symmetries of the permutation in a PermSet, all possible
        combinations of revers, complement and inverse.
        """
        syms = set([self, self.inverse()])
        curr = self
        for _ in range(3):
            curr = curr.rotate()
            syms.add(curr)
            syms.add(curr.inverse())
        return tuple(syms)

    def is_representative(self):
        """Checks if the permutation is representative, that is, all the
        symmetries of the permutation are the same.
        """
        # return self == sorted(self.all_syms())[0]
        pass

    #
    # Statistical methods
    #

    def is_increasing(self):
        """Return True if the perm is increasing, and False otherwise."""
        for index in range(len(self)):
            if self[index] != index:
                return False
        return True

    def is_decreasing(self):
        """Return True if the perm is decreasing, and False otherwise."""
        len_perm = len(self)
        for index in range(len_perm):
            if self[index] != len_perm - index - 1:
                return False
        return True

    def count_fixed_points(self):
        """Return the number of fixed points in self.

        Examples:
            >>> Perm((0, 1, 4, 3, 2)).count_fixed_points()
            3
            >>> Perm((0, 1, 2, 3, 4)).count_fixed_points()
            5
            >>> Perm((3, 2, 1, 0)).count_fixed_points()
            0
        """
        return sum(1 for _ in self.fixed_points())

    def fixed_points(self):
        """Yield the index of the fixed points in self.

        Examples:
            >>> tuple(Perm((0, 2, 1, 3)).fixed_points())
            (0, 3)
            >>> tuple(Perm((0, 1, 4, 3, 2)).fixed_points())
            (0, 1, 3)
        """
        for idx, val in enumerate(self):
            if idx == val:
                yield idx

    def strong_fixed_points(self):
        """Yield the index of the strong fixed points in self.

        Examples:
            >>> tuple(Perm((0, 2, 1, 3)).strong_fixed_points())
            (0, 3)
            >>> tuple(Perm((0, 1, 4, 3, 2)).strong_fixed_points())
            (0, 1)
        """
        if self != Perm(()):
            L = len(self)
            curmax = self[0]
            for idx, val in enumerate(self):
                if idx == val:
                    if val >= curmax:
                        if idx == L - 1 or val < min(
                            self[i] for i in range(idx + 1, L)
                        ):
                            yield idx

    def is_skew_decomposable(self):
        """Determines whether the permutation is expressible as the skew sum of
        two permutations.

        >>> p = Perm.random(8).direct_sum(Perm.random(12))
        >>> p.skew_decomposable()
        False
        >>> p.complement().skew_decomposable()
        True
        """

        p = list(self)
        n = self.__len__()
        for i in range(1, n):
            if set(range(n - i, n)) == set(p[0:i]):
                return True
        return False

    skew_decomposable = is_skew_decomposable  # permpy backwards compatibility

    def is_sum_decomposable(self):
        """Determines whether the permutation is expressible as the direct sum of
        two permutations.

        >>> p = Perm.random(4).direct_sum(Perm.random(15))
        >>> p.sum_decomposable()
        True
        >>> p.reverse().sum_decomposable()
        False
        """

        p = list(self)
        n = self.__len__()
        for i in range(1, n):
            if set(range(0, i)) == set(p[0:i]):
                return True
        return False

    sum_decomposable = is_sum_decomposable  # permpy backwards compatibility

    def descents(self):
        """Yield the 0-based descents of self.

        Examples:
            >>> tuple(Perm((0, 1, 3, 2, 4)).descents())
            (2,)
            >>> tuple(Perm((3, 2, 1, 0)).descents())
            (0, 1, 2)
            >>> tuple(Perm((0, 1, 2)).descents())
            ()
        """
        for index in range(len(self) - 1):
            if self[index] > self[index + 1]:
                yield index

    def descent_set(self):
        """Return the list of descents of self.

        This method is for backwards compatibility with permpy.
        """
        return list(self.descents())

    def count_descents(self):
        """Count the number of descents of self.
        Examples:
            >>> Perm((0, 1, 3, 2, 4)).count_descents()
            1
            >>> Perm((3, 2, 1, 0)).count_descents()
            3
            >>> Perm((0, 1, 2)).count_descents()
            0
        """
        return sum(1 for _ in self.descents())

    num_descents = count_descents  # permpy backwards compatibility

    def ascents(self):
        """Yield the 0-based ascent of self.

        Examples:
            >>> tuple(Perm((0, 1, 3, 2, 4)).ascents())
            (0, 1, 3)
            >>> tuple(Perm((0, 4, 3, 2, 1)).ascents())
            (0,)
            >>> tuple(Perm((3, 2, 1, 0)).ascents())
            ()
        """
        for index in range(len(self) - 1):
            if self[index] < self[index + 1]:
                yield index

    def ascent_set(self):
        """Return the list of ascents of self.

        This method is for backwards compatibility with permpy.
        """
        return list(self.ascents())

    def count_ascents(self):
        """Count the number of ascents in self.

        Examples:
            >>> Perm((0, 1, 3, 2, 4)).count_ascents()
            3
            >>> Perm((0, 4, 3, 2, 1)).count_ascents()
            1
            >>> Perm((3, 2, 1, 0)).count_ascents()
            0
        """
        return sum(1 for _ in self.ascents())

    num_ascents = count_ascents  # permpy backwards compatibility

    def peaks(self):
        """Yield the indices of the peaks of self.

        The i-th element of a perm is a peak if
            self[i-1] < self[i] > self[i+1].

        Examples:
            >>> tuple(Perm((5, 3, 4, 0, 2, 1)).peaks())
            (2, 4)
            >>> tuple(Perm((1, 2, 0)).peaks())
            (1,)
            >>> tuple(Perm((2, 1, 0)).peaks())
            ()
        """
        if len(self) <= 2:
            return
        ascent = False
        for index in range(1, len(self) - 1):
            if self[index - 1] < self[index]:
                # Perm ascended
                ascent = True
            else:
                # Perm descended
                if ascent:
                    yield index - 1
                ascent = False
        # Check if penultimate element is a peak
        if ascent and self[-2] > self[-1]:
            yield len(self) - 2

    def peak_list(self):
        """Return the list of peaks of self.

        This method is for backwards compatibility with permpy.
        """
        return list(self.peaks())

    def count_peaks(self):
        """Count the number of peaks of self.

        Examples:
            >>> Perm((5, 3, 4, 0, 2, 1)).count_peaks()
            2
            >>> Perm((1, 2, 0)).count_peaks()
            1
            >>> Perm((2, 1, 0)).count_peaks()
            0
        """
        return sum(1 for _ in self.peaks())

    num_peaks = count_peaks  # permpy backwards compatibility

    def valleys(self):
        """Yield the indices of the valleys of self.

        The i-th element of a perm is a valley if
            self[i-1] > self[i] < self[i+1].

        Examples:
            >>> tuple(Perm((5, 3, 4, 0, 2, 1)).valleys())
            (1, 3)
            >>> tuple(Perm((2, 0, 1)).valleys())
            (1,)
            >>> tuple(Perm((1, 2, 0)).valleys())
            ()
        """
        if len(self) <= 2:
            return
        ascent = True
        for index in range(1, len(self) - 1):
            if self[index - 1] < self[index]:
                # Perm ascended
                if not ascent:
                    yield index - 1
                ascent = True
            else:
                # Perm descended
                ascent = False
        # Check if penultimate element is a valley
        if not ascent and self[-2] < self[-1]:
            yield len(self) - 2

    def valley_list(self):
        """Return the list of valleys of self.

        This method is for backwards compatibility with permpy.
        """
        return list(self.valleys())

    def count_valleys(self):
        """Count the number of valleys of self.

        Examples:
            >>> Perm((5, 3, 4, 0, 2, 1)).count_valleys()
            2
            >>> Perm((2, 0, 1)).count_valleys()
            1
            >>> Perm((1, 2, 0)).count_valleys()
            0
        """
        return sum(1 for _ in self.valleys())

    num_valleys = count_valleys  # permpy backwards compatibility

    def bends(self):
        """Yield the indices at which the permutation changes direction. That
        is, the number of non-monotone consecutive triples of the permutation.
        A permutation p can be expressed as the concatenation of len(p.bends())
        + 1 monotone segments.

        Examples:
            >>> list(Perm((5, 3, 4, 0, 2, 1)).bends())
            [1, 2, 3, 4]
            >>> list(Perm((2, 0, 1)).bends())
            [1]
        """
        if len(self) <= 2:
            return
        ascent = self[0] < self[1]
        for index in range(1, len(self) - 1):
            if self[index] > self[index + 1] and ascent:
                yield index
            elif self[index] < self[index + 1] and not ascent:
                yield index
            ascent = self[index] < self[index + 1]

    def bend_list(self):
        """Returns the list of indices at which the permutation changes
        direction. That is, the number of non-monotone consecutive triples of
        the permutation. A permutation p can be expressed as the concatenation
        of len(p.bend_list()) + 1 monotone segments.

        Examples:
            >>> Perm((5, 3, 4, 0, 2, 1)).bend_list()
            [1, 2, 3, 4]
            >>> Perm((2, 0, 1)).bend_list()
            [1]
        """
        return list(self.bends())

    def order(self):
        """Returns the order of the permutation.

        Examples:
            >>> Perm((4, 3, 5, 0, 2, 1)).order()
            6
            >>> Perm((0, 1, 2)).order()
            1
        """
        acc = 1
        for l in map(len, self.cycle_decomp()):
            acc = (acc * l) // math.gcd(acc, l)
        return acc

    # TODO: reimplement the following four functions to return generators
    def ltrmin(self):
        """Returns the positions of the left-to-right minima.

        Examples:
            >>> Perm((2, 4, 3, 0, 1)).ltrmin()
            [0, 3]
        """
        L = []
        minval = len(self) + 1
        for idx, val in enumerate(self):
            if val < minval:
                L.append(idx)
                minval = val
        return L

    def rtlmin(self):
        """Returns the positions of the right-to-left minima.

        Examples:
            >>> Perm((2, 0, 4, 1, 5, 3)).rtlmin()
            [1, 3, 5]
        """
        rev_perm = self.reverse()
        return [len(self) - val - 1 for val in rev_perm.ltrmin()][::-1]

    def ltrmax(self):
        """Returns the positions of the left-to-right maxima.

        Examples:
            >>> Perm((2, 0, 4, 1, 5, 3)).ltrmax()
            [0, 2, 4]
        """
        return [len(self) - i - 1 for i in Perm(self[::-1]).rtlmax()][::-1]

    def rtlmax(self):
        """Returns the positions of the right-to-left maxima.

        Examples:
            >>> Perm((2, 4, 3, 0, 1)).rtlmax()
            [1, 2, 4]
        """
        return [len(self) - i - 1 for i in self.complement().reverse().ltrmin()][::-1]

    def count_ltrmin(self):
        """Counts the number of left-to-right minimas.

        Example:
            >>> Perm((2, 4, 3, 0, 1)).count_ltrmin()
            2
        """
        return len(self.ltrmin())

    def count_ltrmax(self):
        """Counts the number of left-to-right minimas.

        Example:
            >>> Perm((2, 4, 3, 0, 1)).count_ltrmin()
            2
        """
        return len(self.ltrmax())

    def count_rtlmin(self):
        """Counts the number of left-to-right minimas.

        Example:
            >>> Perm((2, 4, 3, 0, 1)).count_ltrmin()
            2
        """
        return len(self.rtlmin())

    def count_rtlmax(self):
        """Counts the number of left-to-right minimas.

        Example:
            >>> Perm((2, 4, 3, 0, 1)).count_ltrmin()
            2
        """
        return len(self.rtlmax())

    num_ltrmin = count_ltrmin

    def count_inversions(self):
        """Returns the number of inversions of the permutation, i.e., the
        number of pairs i,j such that i < j and self(i) > self(j).

        Example:
            >>> Perm((3, 0, 2, 1)).count_inversions()
            4
            >>> Perm.monotone_decreasing(6).count_inversions() == 5*6 / 2
            True
            >>> Perm.monotone_increasing(7).count_inversions()
            0
        """
        bit_len = len(self) + 1
        bit = [0] * bit_len
        for element in reversed(self):
            bit_index = element + 1
            while element:
                bit[0] += bit[element]
                element &= element - 1
            while bit_index < bit_len:
                bit[bit_index] += 1
                bit_index += bit_index & -bit_index
        return bit[0]

    def inversions(self):
        """Yield the inversions of the permutation, i.e., the pairs i,j
        such that i < j and self(i) > self(j).

        TODO: Reimplement in NlogN time.
        Example:
            >>> tuple(Perm((3, 0, 2, 1)).inversions())
            ((0, 1), (0, 2), (0, 3), (2, 3))
        """
        n = len(self)
        for i in range(n):
            for j in range(i + 1, n):
                if self[i] > self[j]:
                    yield (i, j)

    def count_non_inversions(self):
        """Returns the number of non_inversions of the permutation, i.e., the
        number of pairs i,j such that i < j and self[i] < self[j].

        Examples:
            >>> Perm((3, 0, 2, 1, 4)).count_non_inversions()
            6
            >>> Perm.monotone_increasing(7).count_non_inversions() == (6 * 7)/2
            True
        """<commit_msg>more comments<commit_after>import bisect
import collections
import itertools
import math
import numbers
import operator
import random

from .interfaces.flippable import Flippable
from .interfaces.patt import Patt
from .interfaces.rotatable import Rotatable
from .interfaces.shiftable import Shiftable
from .misc.iterable_floor_and_ceiling import left_floor_and_ceiling

__all__ = ("Perm",)


class Perm(tuple, Patt, Rotatable, Shiftable, Flippable):
    """A perm class."""

    _TYPE_ERROR = "'{}' object is not a perm"

    #
    # Methods returning a single Perm instance
    #

    def __new__(cls, iterable=(), check=False):
        """Return a Perm instance.

        Args:
            cls:
                The class of which an instance is requested.
            iterable: <collections.Iterable> or <numbers.Integral>
                An iterable corresponding to a legal perm.
                Also supports passing just a number with unique digits.

        Raises:
            TypeError:
                Bad argument type.
            ValueError:
                Bad argument, but correct type.

        Examples:
            >>> Perm((0, 3, 1, 2))
            Perm((0, 3, 1, 2))
            >>> Perm(range(5, -1, -1))
            Perm((5, 4, 3, 2, 1, 0))
            >>> Perm("abc", check=True)  # Not good
            Traceback (most recent call last):
                ...
            TypeError: ''a'' object is not an integer
        """
        return tuple.__new__(cls, iterable)

    def __init__(self, iterable=(), check=False):
        # Cache for data used when finding occurrences of self in a perm
        self._cached_pattern_details = None
        if check:
            self._init_checked()

    def _init_checked(self):
        """Checks if a suitable iterable given when initialised."""
        used = [False] * len(self)
        for value in self:
            if not isinstance(value, numbers.Integral):
                message = "'{}' object is not an integer".format(repr(value))
                raise TypeError(message)
            if not 0 <= value < len(self):
                raise ValueError("Element out of range: {}".format(value))
            if used[value]:
                raise ValueError("Duplicate element: {}".format(value))
            used[value] = True

    _to_standard_cache = {}

    @classmethod
    def to_standard(cls, iterable):
        """Return the perm corresponding to iterable.

        Duplicate elements are allowed and become consecutive elements (see
        example).

        The standardize alias is supplied for backwards compatibility with
        permpy.  However, the permpy version did not allow for duplicate
        elements.

        Examples:
            >>> Perm.to_standard("a2gsv3")
            Perm((2, 0, 3, 4, 5, 1))
            >>> Perm.to_standard("caaba")
            Perm((4, 0, 1, 3, 2))
        """
        # TODO: Do performance testing
        iterable = tuple(iterable)
        if iterable not in Perm._to_standard_cache:
            result = [None] * len(iterable)
            value = 0
            for (index, _) in sorted(enumerate(iterable), key=operator.itemgetter(1)):
                result[index] = value
                value += 1
            Perm._to_standard_cache[iterable] = cls(result)
        return Perm._to_standard_cache[iterable]

    standardize = to_standard  # permpy backwards compatibility
    from_iterable = to_standard

    @classmethod
    def from_integer(cls, integer):
        """Return the perm corresponding to the integer given. The permutation
        can be given one-based or zero-base but it will be returned in 0-based.

        Examples:
            >>> Perm.from_integer(123)
            Perm((0, 1, 2))
            >>> Perm.from_integer(321)
            Perm((2, 1, 0))
            >>> Perm.from_integer(201)
            Perm((2, 0, 1))
        """
        if isinstance(integer, numbers.Integral):
            if not 0 <= integer <= 9876543210:
                raise ValueError("Illegal perm: {}".format(integer))
            digit_list = []
            if integer == 0:
                digit_list.append(integer)
            else:
                while integer != 0:
                    digit_list.append(integer % 10)
                    integer //= 10
                digit_list.reverse()
            return Perm.to_standard(digit_list)
        else:
            raise TypeError("{} is not an integer".format(repr(integer)))

    @classmethod
    def from_string(cls, string, check=False):
        """Return the perm corresponding to the string given.

        Examples:
            >>> Perm.from_string("203451")
            Perm((2, 0, 3, 4, 5, 1))
            >>> Perm.from_string("40132")
            Perm((4, 0, 1, 3, 2))
        """
        if isinstance(string, str):
            if string == "ε":
                return cls([], check=check)
            else:
                return cls(map(int, string), check=check)
        # TODO: throw exception when not a string

    @classmethod
    def one_based(cls, iterable):
        """A way to enter a perm in the traditional permuta way.

        Examples:
            >>> Perm.one_based((4, 1, 3, 2))
            Perm((3, 0, 2, 1))
        """
        return cls((element - 1 for element in iterable))

    one = one_based
    proper = one_based
    scientific = one_based

    @classmethod
    def identity(cls, length):
        """Return the identity perm of the specified length.

        Examples:
            >>> Perm.identity(0)
            Perm(())
            >>> Perm.identity(4)
            Perm((0, 1, 2, 3))
        """
        return cls(range(length))

    @classmethod
    def random(cls, length):
        """Return a random perm of the specified length.

        Examples:
            >>> perm = Perm.random(8)
            >>> len(perm) == 8
            True
            >>> # TODO: test perm in PermSet(8)
        """
        result = list(range(length))
        random.shuffle(result)
        return cls(result)

    @classmethod
    def monotone_increasing(cls, length):
        """Return a monotone increasing perm of the specified length.

        Examples:
            >>> Perm.monotone_increasing(0)
            Perm(())
            >>> Perm.monotone_increasing(4)
            Perm((0, 1, 2, 3))
        """
        return cls(range(length))

    @classmethod
    def monotone_decreasing(cls, length):
        """Return a monotone decreasing perm of the specified length.

        Examples:
            >>> Perm.monotone_decreasing(0)
            Perm(())
            >>> Perm.monotone_decreasing(4)
            Perm((3, 2, 1, 0))
        """
        return cls(range(length - 1, -1, -1))

    @classmethod
    def unrank(cls, number, length=None):
        """

        Examples:
            >>> Perm.unrank(0)
            Perm(())
            >>> Perm.unrank(1)
            Perm((0,))
            >>> Perm.unrank(2)
            Perm((0, 1))
            >>> Perm.unrank(3)
            Perm((1, 0))
            >>> Perm.unrank(4)
            Perm((0, 1, 2))
            >>> Perm.unrank(5)
            Perm((0, 2, 1))
            >>> Perm.unrank(1, 3)
            Perm((0, 2, 1))
        """
        # TODO: Docstring, and do better? Assertions and messages
        #       Implement readably, nicely, and efficiently
        if length is None:
            # Work out the length and number from the number given
            assert isinstance(number, numbers.Integral)
            assert number >= 0
            if number == 0:
                return cls()
            length = 1
            amount = 1  # Amount of perms of length
            while number > amount:
                number -= amount
                length += 1
                amount *= length
            number -= 1
        else:
            assert isinstance(length, numbers.Integral)
            assert length >= 0
            assert 0 <= number < math.factorial(length)
        return cls(Perm.__unrank(number, length))

    @staticmethod
    def __unrank(number, length):
        candidates = list(range(length))
        for value in range(1, length + 1):
            factorial = math.factorial(length - value)
            division = number // factorial
            yield candidates.pop(division)
            number %= factorial

    ind2perm = unrank  # permpy backwards compatibility

    #
    # Methods modifying/combining Perm instances
    #

    def direct_sum(self, *others):
        """Return the direct sum of two or more perms.

        Args:
            self:
                A perm.
            others: <permuta.Perm> argument list
                Perms.

        Returns: <permuta.Perm>
            The direct sum of all the perms.

        Examples:
            >>> Perm((0,)).direct_sum(Perm((1, 0)))
            Perm((0, 2, 1))
            >>> Perm((0,)).direct_sum(Perm((1, 0)), Perm((2, 1, 0)))
            Perm((0, 2, 1, 5, 4, 3))
        """
        result = list(self)
        shift = len(self)
        for other in others:
            if not isinstance(other, Perm):
                raise TypeError(Perm._TYPE_ERROR.format(repr(other)))
            result.extend(element + shift for element in other)
            shift += len(other)
        return Perm(result)

    def skew_sum(self, *others):
        """Return the skew sum of two or more perms.

        Args:
            self:
                A perm.
            others: <permuta.Perm> argument list
                Perms.

        Returns: <permuta.Perm>
            The skew sum of all the perms.

        Examples:
            >>> Perm((0,)).skew_sum(Perm((0, 1)))
            Perm((2, 0, 1))
            >>> Perm((0,)).skew_sum(Perm((0, 1)), Perm((2, 1, 0)))
            Perm((5, 3, 4, 2, 1, 0))
        """
        shift = sum(len(other) for other in others)
        result = [element + shift for element in self]
        for index in range(len(others)):
            other = others[index]
            if not isinstance(other, Perm):
                raise TypeError(Perm._TYPE_ERROR.format(repr(other)))
            shift -= len(other)
            result.extend(element + shift for element in other)
        return Perm(result)

    def compose(self, *others):
        """Return the composition of two or more perms.

        Args:
            self:
                A perm.
            others: <permuta.Perm> argument list
                Perms.

        Returns: <permuta.Perm>
            The consecutive pointwise application of all the above perms
            in reverse order.

        Raises:
            TypeError:
                An object in the argument list is not a perm.
            ValueError:
                A perm in the argument list is of the wrong length.

        Examples:
            >>> Perm((0, 3, 1, 2)).compose(Perm((2, 1, 0, 3)))
            Perm((1, 3, 0, 2))
            >>> Perm((1, 0, 2)).compose(Perm((0, 1, 2)), Perm((2, 1, 0)))
            Perm((2, 0, 1))
        """
        for other in others:
            if not isinstance(other, Perm):
                raise TypeError(Perm._TYPE_ERROR.format(repr(other)))
            if len(other) != len(self):
                raise ValueError("Perm length mismatch")
        result = [None] * len(self)
        for value in range(len(self)):
            composed_value = value
            for other in reversed(others):
                composed_value = other[composed_value]
            composed_value = self[composed_value]
            result[value] = composed_value
        return Perm(result)

    multiply = compose

    def insert(self, index=None, new_element=None):
        """Return the perm acquired by adding a new element.

        Args:
            index: <int>
                Where in the perm the value is to occur.
                If None, the value defaults to len(self)+1.
            new_element: <int>
                An integer in the range of 0 to len(self) inclusive.
                If None, the element defaults to len(self).

        Returns: <permuta.Perm>
            The perm with the added element (and other elements adjusted
            as needed).

        Raises:
            IndexError:
                Index is not valid.
            ValueError:
                Element passed cannot legally be added to perm.
            TypeError:
                Element passed is not an integer.

        Examples:
            >>> Perm((0, 1)).insert()
            Perm((0, 1, 2))
            >>> Perm((0, 1)).insert(0)
            Perm((2, 0, 1))
            >>> Perm((2, 0, 1)).insert(2, 1)
            Perm((3, 0, 1, 2))
        """
        if index is None:
            index = len(self) + 1
        if new_element is None:
            new_element = len(self)
        else:
            if not isinstance(new_element, numbers.Integral):
                raise TypeError(
                    "'{}' object is not an integer".format(repr(new_element))
                )
            if not 0 <= new_element <= len(self):
                raise ValueError("Element out of range: {}".format(new_element))
        slice_1 = (
            element if element < new_element else element + 1
            for element in itertools.islice(self, index)
        )
        slice_2 = (
            element if element < new_element else element + 1
            for element in itertools.islice(self, index, len(self))
        )
        return Perm(itertools.chain(slice_1, (new_element,), slice_2))

    def remove(self, index=None):
        """Return the perm acquired by removing an element at a specified index.

        Args:
            index: <int>
                The index of the element to be removed.
                If None, the greatest element of the perm is removed.

        Returns: <permuta.Perm>
            The perm without the element (and other elements adjusted).

        Raises:
            IndexError:
                Index is not valid.

        Examples:
            >>> Perm((2, 0, 1)).remove()
            Perm((0, 1))
            >>> Perm((3, 0, 1, 2)).remove(0)
            Perm((0, 1, 2))
            >>> Perm((2, 0, 1)).remove(2)
            Perm((1, 0))
            >>> Perm((0,)).remove(0)
            Perm(())
        """
        if index is None:
            return self.remove_element()
        selected = self[index]
        return Perm(
            element if element < selected else element - 1
            for element in self
            if element != selected
        )

    def remove_element(self, selected=None):
        """Return the perm acquired by removing a specific element from self.

        Args:
            selected: <int>
                The element selected to be removed. It is an integer in the
                range of 0 to len(self) inclusive. If None, it defaults to
                len(self) - 1.

        Returns: <permuta.Perm>
            The perm with the selected element removed (and other
            elements adjusted as needed).

        Raises:
            ValueError:
                Selected element does not belong to perm.
            TypeError:
                Element passed is not an integer.

        Examples:
            >>> Perm((3, 0, 1, 2)).remove_element()
            Perm((0, 1, 2))
            >>> Perm((3, 0, 2, 1)).remove_element(0)
            Perm((2, 1, 0))
        """
        if selected is None:
            selected = len(self) - 1
        else:
            if not isinstance(selected, numbers.Integral):
                raise TypeError("'{}' object is not an integer".format(repr(selected)))
            if not 0 <= selected < len(self):
                raise ValueError("Element out of range: {}".format(selected))
        return Perm(
            element if element < selected else element - 1
            for element in self
            if element != selected
        )

    def inflate(self, components):
        """Inflate elements of the permutation to create a new one.

        Args:
            component: <collections.Iterable> of <permuta.Perm>
                This can also be a dict with keys and perms...

        Returns: <permuta.Perm>

        Examples:
            >>> Perm((0, 1)).inflate([Perm((1, 0)), Perm((2, 1, 0))])
            Perm((1, 0, 4, 3, 2))
            >>> Perm((1, 0, 2)).inflate([None, Perm((0, 1)), Perm((0, 1))])
            Perm((2, 0, 1, 3, 4))
            >>> Perm((0, 2, 1)).inflate({2: Perm((0, 1, 2))})
            Traceback (most recent call last):
                ...
            NotImplementedError
            >>> # Can also deflate points
            >>> Perm((0, 1)).inflate([Perm(), Perm()])
            Perm(())
        """
        # TODO: Spitshine method and docstring
        if isinstance(components, collections.abc.Mapping):
            raise NotImplementedError
        elif isinstance(components, collections.abc.Iterable):
            components = tuple(components)
            assert len(components) == len(self)
            shift = 0
            shifts = [0] * len(self)
            for index in self.inverse():
                shifts[index] = shift
                component = components[index]
                shift += 1 if component is None else len(component)
            perm_elements = []
            for index, component in enumerate(components):
                if component is None:
                    perm_elements.append(shifts[index])
                else:
                    shift = shifts[index]
                    perm_elements.extend(element + shift for element in component)
            return Perm(perm_elements)
        else:
            raise TypeError

    def contract_inc_bonds(self):
        # TODO: test
        monblocks = self.monotone_block_decompositon_ascending(with_ones=True)
        return Perm.to_standard([start for (start, end) in monblocks])

    def contract_dec_bonds(self):
        # TODO: test
        monblocks = self.monotone_block_decompositon_descending(with_ones=True)
        return Perm.to_standard([start for (start, end) in monblocks])

    def contract_bonds(self):
        # TODO: reimplement by calling contract_{inc,dec}_bonds or remove
        pass

    #
    # Methods for basic Perm transforming
    #

    def inverse(self):
        """Return the inverse of the perm self.

        Examples:
            >>> Perm((1, 2, 5, 0, 3, 4)).inverse()
            Perm((3, 0, 1, 4, 5, 2))
            >>> Perm((2, 0, 1)).inverse().inverse() == Perm((2, 0, 1))
            True
            >>> Perm((0, 1)).inverse()
            Perm((0, 1))
        """
        len_perm = len(self)
        result = [None] * len_perm
        for index in range(len_perm):
            result[self[index]] = index
        return Perm(result)

    def reverse(self):
        """Return the reverse of the perm self.

        Examples:
            >>> Perm((1, 2, 5, 0, 3, 4)).reverse()
            Perm((4, 3, 0, 5, 2, 1))
            >>> Perm((0, 1)).reverse()
            Perm((1, 0))
        """
        return Perm(self[::-1])

    def complement(self):
        """Return the complement of the perm self.

        Examples:
            >>> Perm((1, 2, 3, 0, 4)).complement()
            Perm((3, 2, 1, 4, 0))
            >>> Perm((2, 0, 1)).complement()
            Perm((0, 2, 1))
        """
        base = len(self) - 1
        return Perm(base - element for element in self)

    def reverse_complement(self):
        """Return the reverse complement of self.

        Equivalent to two left or right rotations.

        Examples:
            >>> Perm((1, 2, 3, 0, 4)).reverse_complement()
            Perm((0, 4, 1, 2, 3))
            >>> Perm((2, 0, 1)).reverse_complement()
            Perm((1, 2, 0))
        """
        base = len(self) - 1
        return Perm(base - element for element in reversed(self))

    def shift_right(self, times=1):
        """Return self shifted times steps to the right.

        If shift is negative, shifted to the left.

        Examples:
            >>> Perm((0, 1, 2)).shift_right()
            Perm((2, 0, 1))
            >>> Perm((0, 1, 2)).shift_right(-4)
            Perm((1, 2, 0))
        """
        if len(self) == 0:
            return self
        times = times % len(self)
        if times == 0:
            return self
        index = len(self) - times
        slice_1 = itertools.islice(self, index)
        slice_2 = itertools.islice(self, index, len(self))
        return Perm(itertools.chain(slice_2, slice_1))

    def shift_left(self, times=1):
        """Return self shifted times steps to the left.

        If shift is negative, shifted to the right.

        Examples:
            >>> Perm((0, 1, 2)).shift_left()
            Perm((1, 2, 0))
            >>> Perm((0, 1, 2)).shift_left(-4)
            Perm((2, 0, 1))
        """
        return self.shift_right(-times)

    shift = shift_right
    cyclic_shift = shift_right
    cyclic_shift_right = shift_right
    cyclic_shift_left = shift_left

    def shift_up(self, times=1):
        """Return self shifted times steps up.

        If times is negative, shifted down.

        Examples:
            >>> Perm((0, 1, 2, 3)).shift_up(1)
            Perm((1, 2, 3, 0))
            >>> Perm((0, 1, 2, 3)).shift_up(-7)
            Perm((1, 2, 3, 0))
            >>> Perm((0,)).shift_up(1234)
            Perm((0,))
        """
        if len(self) == 0:
            return self
        times = times % len(self)
        if times == 0:
            return self
        bound = len(self)
        return Perm((element + times) % bound for element in self)

    def shift_down(self, times=1):
        """Return self shifted times steps down.

        If times is negative, shifted up.

        Examples:
            >>> Perm((0, 1, 2, 3)).shift_down(1)
            Perm((3, 0, 1, 2))
            >>> Perm((0, 1, 2, 3)).shift_down(-7)
            Perm((3, 0, 1, 2))
            >>> Perm((0,)).shift_down(1234)
            Perm((0,))
        """
        return self.shift_up(-times)

    def flip_horizontal(self):
        """Return self flipped horizontally.

        Examples:
            >>> Perm((1, 2, 3, 0, 4)).flip_horizontal()
            Perm((3, 2, 1, 4, 0))
            >>> Perm((2, 0, 1)).flip_horizontal()
            Perm((0, 2, 1))
        """
        return self.complement()

    def flip_vertical(self):
        """Return self flipped vertically.

        Examples:
            >>> Perm((1, 2, 5, 0, 3, 4)).flip_vertical()
            Perm((4, 3, 0, 5, 2, 1))
            >>> Perm((0, 1)).flip_vertical()
            Perm((1, 0))
        """
        return self.reverse()

    def flip_diagonal(self):
        """Return self flipped along the diagonal.

        Examples:
            >>> Perm((1, 2, 5, 0, 3, 4)).flip_diagonal()
            Perm((3, 0, 1, 4, 5, 2))
            >>> Perm((0, 1)).flip_diagonal()
            Perm((0, 1))
        """
        return self.inverse()

    def flip_antidiagonal(self):
        """Return self flipped along the antidiagonal..

        Examples:
            >>> Perm((3, 2, 0, 1)).flip_antidiagonal()
            Perm((3, 2, 0, 1))
            >>> Perm((1, 2, 3, 0, 4)).flip_antidiagonal()
            Perm((0, 2, 3, 4, 1))
            >>> Perm((1, 2, 0, 3)).flip_antidiagonal()
            Perm((0, 2, 3, 1))
        """
        len_perm = len(self)
        result = [None] * len_perm

        flipped_pairs = (
            (len_perm - element - 1, len_perm - index - 1)
            for index, element in enumerate(self)
        )

        for index, element in flipped_pairs:
            result[index] = element
        return Perm(result)

    def _rotate_right(self):
        """Return self rotated 90 degrees to the right."""
        len_perm = len(self)
        result = [None] * len_perm
        for index, value in enumerate(self):
            result[value] = len_perm - index - 1
        return Perm(result)

    def _rotate_left(self):
        """Return self rotated 90 degrees to the left."""
        len_perm = len(self)
        result = [None] * len_perm
        for index, value in enumerate(self):
            result[len_perm - value - 1] = index
        return Perm(result)

    def _rotate_180(self):
        """Return self rotated 180 degrees."""
        return self.reverse_complement()

    def all_syms(self):
        """Returns all symmetries of the permutation in a PermSet, all possible
        combinations of revers, complement and inverse.
        """
        syms = set([self, self.inverse()])
        curr = self
        for _ in range(3):
            curr = curr.rotate()
            syms.add(curr)
            syms.add(curr.inverse())
        return tuple(syms)

    def is_representative(self):
        """Checks if the permutation is representative, that is, all the
        symmetries of the permutation are the same.
        """
        # return self == sorted(self.all_syms())[0]
        pass

    #
    # Statistical methods
    #

    def is_increasing(self):
        """Return True if the perm is increasing, and False otherwise."""
        for index in range(len(self)):
            if self[index] != index:
                return False
        return True

    def is_decreasing(self):
        """Return True if the perm is decreasing, and False otherwise."""
        len_perm = len(self)
        for index in range(len_perm):
            if self[index] != len_perm - index - 1:
                return False
        return True

    def count_fixed_points(self):
        """Return the number of fixed points in self.

        Examples:
            >>> Perm((0, 1, 4, 3, 2)).count_fixed_points()
            3
            >>> Perm((0, 1, 2, 3, 4)).count_fixed_points()
            5
            >>> Perm((3, 2, 1, 0)).count_fixed_points()
            0
        """
        return sum(1 for _ in self.fixed_points())

    def fixed_points(self):
        """Yield the index of the fixed points in self.

        Examples:
            >>> tuple(Perm((0, 2, 1, 3)).fixed_points())
            (0, 3)
            >>> tuple(Perm((0, 1, 4, 3, 2)).fixed_points())
            (0, 1, 3)
        """
        for idx, val in enumerate(self):
            if idx == val:
                yield idx

    def strong_fixed_points(self):
        """Yield the index of the strong fixed points in self.

        Examples:
            >>> tuple(Perm((0, 2, 1, 3)).strong_fixed_points())
            (0, 3)
            >>> tuple(Perm((0, 1, 4, 3, 2)).strong_fixed_points())
            (0, 1)
        """
        if self != Perm(()):
            L = len(self)
            curmax = self[0]
            for idx, val in enumerate(self):
                if idx == val:
                    if val >= curmax:
                        if idx == L - 1 or val < min(
                            self[i] for i in range(idx + 1, L)
                        ):
                            yield idx

    def is_skew_decomposable(self):
        """Determines whether the permutation is expressible as the skew sum of
        two permutations.

        >>> p = Perm.random(8).direct_sum(Perm.random(12))
        >>> p.skew_decomposable()
        False
        >>> p.complement().skew_decomposable()
        True
        """

        p = list(self)
        n = self.__len__()
        for i in range(1, n):
            if set(range(n - i, n)) == set(p[0:i]):
                return True
        return False

    skew_decomposable = is_skew_decomposable  # permpy backwards compatibility

    def is_sum_decomposable(self):
        """Determines whether the permutation is expressible as the direct sum of
        two permutations.

        >>> p = Perm.random(4).direct_sum(Perm.random(15))
        >>> p.sum_decomposable()
        True
        >>> p.reverse().sum_decomposable()
        False
        """

        p = list(self)
        n = self.__len__()
        for i in range(1, n):
            if set(range(0, i)) == set(p[0:i]):
                return True
        return False

    sum_decomposable = is_sum_decomposable  # permpy backwards compatibility

    def descents(self):
        """Yield the 0-based descents of self.

        Examples:
            >>> tuple(Perm((0, 1, 3, 2, 4)).descents())
            (2,)
            >>> tuple(Perm((3, 2, 1, 0)).descents())
            (0, 1, 2)
            >>> tuple(Perm((0, 1, 2)).descents())
            ()
        """
        for index in range(len(self) - 1):
            if self[index] > self[index + 1]:
                yield index

    def descent_set(self):
        """Return the list of descents of self.

        This method is for backwards compatibility with permpy.
        """
        return list(self.descents())

    def count_descents(self):
        """Count the number of descents of self.
        Examples:
            >>> Perm((0, 1, 3, 2, 4)).count_descents()
            1
            >>> Perm((3, 2, 1, 0)).count_descents()
            3
            >>> Perm((0, 1, 2)).count_descents()
            0
        """
        return sum(1 for _ in self.descents())

    num_descents = count_descents  # permpy backwards compatibility

    def ascents(self):
        """Yield the 0-based ascent of self.

        Examples:
            >>> tuple(Perm((0, 1, 3, 2, 4)).ascents())
            (0, 1, 3)
            >>> tuple(Perm((0, 4, 3, 2, 1)).ascents())
            (0,)
            >>> tuple(Perm((3, 2, 1, 0)).ascents())
            ()
        """
        for index in range(len(self) - 1):
            if self[index] < self[index + 1]:
                yield index

    def ascent_set(self):
        """Return the list of ascents of self.

        This method is for backwards compatibility with permpy.
        """
        return list(self.ascents())

    def count_ascents(self):
        """Count the number of ascents in self.

        Examples:
            >>> Perm((0, 1, 3, 2, 4)).count_ascents()
            3
            >>> Perm((0, 4, 3, 2, 1)).count_ascents()
            1
            >>> Perm((3, 2, 1, 0)).count_ascents()
            0
        """
        return sum(1 for _ in self.ascents())

    num_ascents = count_ascents  # permpy backwards compatibility

    def peaks(self):
        """Yield the indices of the peaks of self.

        The i-th element of a perm is a peak if
            self[i-1] < self[i] > self[i+1].

        Examples:
            >>> tuple(Perm((5, 3, 4, 0, 2, 1)).peaks())
            (2, 4)
            >>> tuple(Perm((1, 2, 0)).peaks())
            (1,)
            >>> tuple(Perm((2, 1, 0)).peaks())
            ()
        """
        if len(self) <= 2:
            return
        ascent = False
        for index in range(1, len(self) - 1):
            if self[index - 1] < self[index]:
                # Perm ascended
                ascent = True
            else:
                # Perm descended
                if ascent:
                    yield index - 1
                ascent = False
        # Check if penultimate element is a peak
        if ascent and self[-2] > self[-1]:
            yield len(self) - 2

    def peak_list(self):
        """Return the list of peaks of self.

        This method is for backwards compatibility with permpy.
        """
        return list(self.peaks())

    def count_peaks(self):
        """Count the number of peaks of self.

        Examples:
            >>> Perm((5, 3, 4, 0, 2, 1)).count_peaks()
            2
            >>> Perm((1, 2, 0)).count_peaks()
            1
            >>> Perm((2, 1, 0)).count_peaks()
            0
        """
        return sum(1 for _ in self.peaks())

    num_peaks = count_peaks  # permpy backwards compatibility

    def valleys(self):
        """Yield the indices of the valleys of self.

        The i-th element of a perm is a valley if
            self[i-1] > self[i] < self[i+1].

        Examples:
            >>> tuple(Perm((5, 3, 4, 0, 2, 1)).valleys())
            (1, 3)
            >>> tuple(Perm((2, 0, 1)).valleys())
            (1,)
            >>> tuple(Perm((1, 2, 0)).valleys())
            ()
        """
        if len(self) <= 2:
            return
        ascent = True
        for index in range(1, len(self) - 1):
            if self[index - 1] < self[index]:
                # Perm ascended
                if not ascent:
                    yield index - 1
                ascent = True
            else:
                # Perm descended
                ascent = False
        # Check if penultimate element is a valley
        if not ascent and self[-2] < self[-1]:
            yield len(self) - 2

    def valley_list(self):
        """Return the list of valleys of self.

        This method is for backwards compatibility with permpy.
        """
        return list(self.valleys())

    def count_valleys(self):
        """Count the number of valleys of self.

        Examples:
            >>> Perm((5, 3, 4, 0, 2, 1)).count_valleys()
            2
            >>> Perm((2, 0, 1)).count_valleys()
            1
            >>> Perm((1, 2, 0)).count_valleys()
            0
        """
        return sum(1 for _ in self.valleys())

    num_valleys = count_valleys  # permpy backwards compatibility

    def bends(self):
        """Yield the indices at which the permutation changes direction. That
        is, the number of non-monotone consecutive triples of the permutation.
        A permutation p can be expressed as the concatenation of len(p.bends())
        + 1 monotone segments.

        Examples:
            >>> list(Perm((5, 3, 4, 0, 2, 1)).bends())
            [1, 2, 3, 4]
            >>> list(Perm((2, 0, 1)).bends())
            [1]
        """
        if len(self) <= 2:
            return
        ascent = self[0] < self[1]
        for index in range(1, len(self) - 1):
            if self[index] > self[index + 1] and ascent:
                yield index
            elif self[index] < self[index + 1] and not ascent:
                yield index
            ascent = self[index] < self[index + 1]

    def bend_list(self):
        """Returns the list of indices at which the permutation changes
        direction. That is, the number of non-monotone consecutive triples of
        the permutation. A permutation p can be expressed as the concatenation
        of len(p.bend_list()) + 1 monotone segments.

        Examples:
            >>> Perm((5, 3, 4, 0, 2, 1)).bend_list()
            [1, 2, 3, 4]
            >>> Perm((2, 0, 1)).bend_list()
            [1]
        """
        return list(self.bends())

    def order(self):
        """Returns the order of the permutation.

        Examples:
            >>> Perm((4, 3, 5, 0, 2, 1)).order()
            6
            >>> Perm((0, 1, 2)).order()
            1
        """
        acc = 1
        for l in map(len, self.cycle_decomp()):
            acc = (acc * l) // math.gcd(acc, l)
        return acc

    # TODO: reimplement the following four functions to return generators
    def ltrmin(self):
        """Returns the positions of the left-to-right minima.

        Examples:
            >>> Perm((2, 4, 3, 0, 1)).ltrmin()
            [0, 3]
        """
        L = []
        minval = len(self) + 1
        for idx, val in enumerate(self):
            if val < minval:
                L.append(idx)
                minval = val
        return L

    def rtlmin(self):
        """Returns the positions of the right-to-left minima.

        Examples:
            >>> Perm((2, 0, 4, 1, 5, 3)).rtlmin()
            [1, 3, 5]
        """
        rev_perm = self.reverse()
        return [len(self) - val - 1 for val in rev_perm.ltrmin()][::-1]

    def ltrmax(self):
        """Returns the positions of the left-to-right maxima.

        Examples:
            >>> Perm((2, 0, 4, 1, 5, 3)).ltrmax()
            [0, 2, 4]
        """
        return [len(self) - i - 1 for i in Perm(self[::-1]).rtlmax()][::-1]

    def rtlmax(self):
        """Returns the positions of the right-to-left maxima.

        Examples:
            >>> Perm((2, 4, 3, 0, 1)).rtlmax()
            [1, 2, 4]
        """
        return [len(self) - i - 1 for i in self.complement().reverse().ltrmin()][::-1]

    def count_ltrmin(self):
        """Counts the number of left-to-right minimas.

        Example:
            >>> Perm((2, 4, 3, 0, 1)).count_ltrmin()
            2
        """
        return len(self.ltrmin())

    def count_ltrmax(self):
        """Counts the number of left-to-right minimas.

        Example:
            >>> Perm((2, 4, 3, 0, 1)).count_ltrmin()
            2
        """
        return len(self.ltrmax())

    def count_rtlmin(self):
        """Counts the number of left-to-right minimas.

        Example:
            >>> Perm((2, 4, 3, 0, 1)).count_ltrmin()
            2
        """
        return len(self.rtlmin())

    def count_rtlmax(self):
        """Counts the number of left-to-right minimas.

        Example:
            >>> Perm((2, 4, 3, 0, 1)).count_ltrmin()
            2
        """
        return len(self.rtlmax())

    num_ltrmin = count_ltrmin

    def count_inversions(self):
        """Returns the number of inversions of the permutation, i.e., the
        number of pairs i,j such that i < j and self(i) > self(j).

        Example:
            >>> Perm((3, 0, 2, 1)).count_inversions()
            4
            >>> Perm.monotone_decreasing(6).count_inversions() == 5*6 / 2
            True
            >>> Perm.monotone_increasing(7).count_inversions()
            0
        """
        bit_len = len(self) + 1
        bit = [0] * bit_len
        for element in reversed(self):
            bit_index = element + 1
            # Count lesser elements to the right
            while element:
                bit[0] += bit[element]
                # Flip the right most set bit
                element &= element - 1
            # Increment frequency for current element
            while bit_index < bit_len:
                bit[bit_index] += 1
                # Increase index by the largest power of two that divides it
                bit_index += bit_index & -bit_index
        return bit[0]

    def inversions(self):
        """Yield the inversions of the permutation, i.e., the pairs i,j
        such that i < j and self(i) > self(j).

        TODO: Reimplement in NlogN time.
        Example:
            >>> tuple(Perm((3, 0, 2, 1)).inversions())
            ((0, 1), (0, 2), (0, 3), (2, 3))
        """
        n = len(self)
        for i in range(n):
            for j in range(i + 1, n):
                if self[i] > self[j]:
                    yield (i, j)

    def count_non_inversions(self):
        """Returns the number of non_inversions of the permutation, i.e., the
        number of pairs i,j such that i < j and self[i] < self[j].

        Examples:
            >>> Perm((3, 0, 2, 1, 4)).count_non_inversions()
            6
            >>> Perm.monotone_increasing(7).count_non_inversions() == (6 * 7)/2
            True
        """
{'fraction_non_alphanumeric': 0.12248062015503876, 'fraction_numerical': 0.024470284237726098, 'mean_word_length': 1.572145420709823, 'pattern_counts': {'":': 2, '<': 105, '<?xml version=': 0, '>': 855, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '569966', 'n_tokens_mistral': 23688, 'n_tokens_neox': 21563, 'n_words': 6839}