# Source code for permutation

"""
Permutations of finitely many positive integers

permutation provides a Permutation class for representing permutations
<https://en.wikipedia.org/wiki/Permutation>_ of finitely many positive
integers in Python.  Supported operations & properties include inverses, (group
theoretic) order, parity, composition/multiplication, cycle decomposition,
cycle notation, word representation, Lehmer codes, and, of course, use as a
callable on integers.

Visit <https://github.com/jwodder/permutation> or <http://permutation.rtfd.io>
"""

__version__      = '0.2.0'
__author__       = 'John Thorvald Wodder II'
__author_email__ = 'permutation@varonathe.org'
__url__          = 'https://github.com/jwodder/permutation'

from   functools import reduce
from   itertools import starmap
import operator
import re

try:
# Importing fractions.gcd unconditionally produces a DeprecationWarning in
# 3.5+, so we need to use math.gcd whenever it's available.
from math      import gcd
except ImportError:
from fractions import gcd

__all__ = ["Permutation"]

[docs]class Permutation(object):
r"""
A Permutation object represents a permutation
<https://en.wikipedia.org/wiki/Permutation>_ of finitely many positive
integers, i.e., a bijective function from some integer range :math:[1,n]
to itself.

The arguments to the constructor are the elements of the permutation's word
representation, i.e., the images of the integers 1 through some :math:n
under the permutation.  For example, Permutation(5, 4, 3, 6, 1, 2) is
the permutation that maps 1 to 5, 2 to 4, 3 to itself, 4 to 6, 5 to 1, and
6 to 2.  Permutation() (with no arguments) evaluates to the identity
permutation (i.e., the permutation that returns all inputs unchanged).

Permutation\ s are hashable and immutable.  They can be compared for
equality but not for ordering/sorting.
"""

[docs]    def __init__(self, *img):
d = len(img)
used = [False] * d
for i in img:
if i < 1:
raise ValueError('values must be positive')
if i > d:
raise ValueError('value missing from input')
if used[i-1]:
raise ValueError('value repeated in input')
used[i-1] = True
while d > 0 and img[d-1] == d:
d -= 1
self.__map = img[:d]

[docs]    def __call__(self, i):
"""
Map an integer through the permutation.  Values less than 1 are
returned unchanged.

:param int i:
:return: the image of i under the permutation
"""
return self.__map[i-1] if 0 < i <= len(self.__map) else i

[docs]    def __mul__(self, other):
"""
Multiplication/composition of permutations.  p * q returns a
Permutation r such that r(x) == p(q(x)) for all integers
x.

:param Permutation other:
:rtype: Permutation
"""
return type(self)(*(self(other(i+1))
for i in range(max(self.degree, other.degree))))

[docs]    def __repr__(self):
return '{0.__module__}.{0.__name__}{1!r}'.format(type(self), self.__map)

[docs]    def __str__(self):
"""
Convert a Permutation to cycle notation
<https://en.wikipedia.org/wiki/Permutation#Cycle_notation>_.  The
instance is decomposed into cycles with to_cycles(), each cycle is
written as a parenthesized space-separated sequence of integers, and
the cycles are concatenated.

str(Permutation()) is "1".

This is the inverse of parse.

>>> str(Permutation(2, 5, 4, 3, 1))
'(1 2 5)(3 4)'
"""
return ''.join(
'(' + ' '.join(map(str,cyc)) + ')' for cyc in self.to_cycles()
) or '1'

[docs]    @classmethod
def parse(cls, s):
"""
Parse a permutation written in cycle notation.  This is the inverse of
__str__.

:param str s: a permutation written in cycle notation
:return: the permutation represented by s
:rtype: Permutation
:raises ValueError: if s is not valid cycle notation for a
permutation
"""
s = s.strip()
if s == '1':
return cls()
if not (s.startswith('(') and s.endswith(')')):
raise ValueError(s)
cycles = []
for cyc in re.split(r'\)[\s,]*\(', s[1:-1]):
cyc = cyc.strip()
if cyc:
cycles.append(map(int, re.split(r'\s*,\s*|\s+', cyc)))
return cls.from_cycles(*cycles)

[docs]    def __nonzero__(self):
""" A Permutation is true iff it is not the identity """
return self.__map != ()

__bool__ = __nonzero__

[docs]    def __eq__(self, other):
if type(self) is type(other):
return self.__map == other.__map
else:
return NotImplemented

[docs]    def __ne__(self, other):
return not (self == other)

[docs]    def __hash__(self):
return hash(self.__map)

@property
def degree(self):
"""
The degree of the permutation, i.e., the largest integer that it
permutes (does not map to itself), or 0 if there is no such integer
(i.e., if the permutation is the identity)
"""
return len(self.__map)

[docs]    def inverse(self):
"""
Returns the inverse of the permutation, i.e., the unique permutation
that, when multiplied by the invocant on either the left or the right,
produces the identity

:rtype: Permutation
"""
return type(self)(*self.permute(range(1, self.degree+1)))

@property
def order(self):
"""
The order <https://en.wikipedia.org/wiki/Order_(group_theory)>_
(a.k.a. period) of the permutation, i.e., the smallest positive integer
:math:n such that multiplying :math:n copies of the permutation
together produces the identity
"""
return reduce(lcm, map(len, self.to_cycles()), 1)

@property
def is_even(self):
"""
Whether the permutation is even, i.e., can be expressed as the product
of an even number of transpositions (cycles of length 2)
"""
return not sum((len(cyc)-1 for cyc in self.to_cycles()),0) % 2

@property
def is_odd(self):
""" Whether the permutation is odd, i.e., not even """
return not self.is_even

@property
def sign(self):
"""
The sign (a.k.a. signature) of the permutation: 1 if the permutation is
even, -1 if it is odd
"""
return 1 if self.is_even else -1

[docs]    def right_inversion_count(self, n=None):
"""

Calculate the right inversion count_ or right inversion vector of the
permutation through degree n, or through degree if n is
unspecified.  The result is a list of n elements in which the
element at index i corresponds to the number of right inversions
for i+1, i.e., the number of values x > i+1 for which p(x) <
p(i+1).

Setting n larger than degree causes the resulting list to have
trailing zeroes, which become relevant when converting to & from Lehmer
codes and factorial base.

.. _right inversion count: https://en.wikipedia.org/wiki/Inversion_(discrete_mathematics)#Inversion_related_vectors

:param int n: defaults to degree
:rtype: list of int
:raises ValueError: if n is less than degree
"""
if n is None:
n = self.degree
elif n < self.degree:
raise ValueError(n)
left = list(range(1, n+1))
digits = []
for x in left[:]:
i = left.index(self(x))
del left[i]
digits.append(i)
return digits

[docs]    def lehmer(self, n):
"""
Calculate the Lehmer code
<https://en.wikipedia.org/wiki/Lehmer_code>_ of the permutation with
respect to all permutations of degree at most n.  This is the
(zero-based) index of the permutation in the list of all permutations
of degree at most n ordered lexicographically by word
representation.

This is the inverse of from_lehmer.

:param int n:
:rtype: int
:raises ValueError: if n is less than degree
"""
return from_factorial_base(self.right_inversion_count(n)[:-1])

[docs]    @classmethod
def from_lehmer(cls, x, n):
"""
Calculate the permutation in :math:S_n with Lehmer code x.  This
is the permutation at index x (zero-based) in the list of all
permutations of degree at most n ordered lexicographically by word
representation.

This is the inverse of lehmer.

:param int x: a nonnegative integer
:param int n: the degree of the symmetric group with respect to which
x was calculated
:return: the Permutation with Lehmer code x
:raises ValueError: if x is less than 0 or greater than or equal to
the factorial of n
"""
if x < 0:
raise ValueError(x)
mapping = []
x2 = x
for i in range(1, n+1):
x2, c = divmod(x2, i)
for (j,y) in enumerate(mapping):
if y >= c:
mapping[j] += 1
mapping.insert(0,c)
if x2 != 0:
raise ValueError(x)
return cls(*(c+1 for c in mapping))

[docs]    def left_lehmer(self):
"""
Encode the permutation as a nonnegative integer using a modified form
of Lehmer codes <https://en.wikipedia.org/wiki/Lehmer_code>_ that
uses the left inversion count <inversion_>_ instead of the right
inversion count.  This modified encoding establishes a
degree-independent bijection between permutations and nonnegative
integers, with from_left_lehmer() converting values in the opposite
direction.

.. _inversion: https://en.wikipedia.org/wiki/Inversion_(discrete_mathematics)#Inversion_related_vectors

:return: the permutation's left Lehmer code
:rtype: int
"""
left = list(range(self.degree, 0, -1))
digits = []
for x in left[:]:
i = left.index(self(x))
del left[i]
digits.append(i)
return from_factorial_base(digits[:-1])

[docs]    @classmethod
def from_left_lehmer(cls, x):
"""
Returns the permutation with the given left Lehmer code.  This is the
inverse of left_lehmer().

:param int x: a nonnegative integer
:return: the Permutation with left Lehmer code x
:raises ValueError: if x is less than 0
"""
if x < 0:
raise ValueError(x)
mapping = 
for c in reversed(to_factorial_base(x)):
for (i,y) in enumerate(mapping):
if y >= c:
mapping[i] += 1
mapping.append(c)
return cls(*(len(mapping)-c for c in mapping))

[docs]    def to_cycles(self):
"""
Decompose the permutation into a product of disjoint cycles.
to_cycles() returns a list of cycles in which each cycle is a tuple
of integers.  Each cycle c is a sub-permutation that maps c
to c, c to c, etc., finally mapping c[-1] back
around to c.  The permutation is then the product of these
cycles.

Each cycle is at least two elements in length and places its smallest
element first.  Cycles are ordered by their first elements in
increasing order.  No two cycles share an element.

When the permutation is the identity, to_cycles() returns an empty
list.

This is the inverse of from_cycles.

:return: the cycle decomposition of the permutation
"""
cmap = list(self.__map)
cycles = []
for i in range(len(cmap)):
if cmap[i] not in (0, i+1):
x = i+1
cyke = []
while True:
cyke.append(x)
cmap[x-1], x = 0, cmap[x-1]
if x == i+1:
break
cycles.append(tuple(cyke))
return cycles

[docs]    @classmethod
def cycle(cls, *cyc):
"""
Construct a cyclic permutation
<https://en.wikipedia.org/wiki/Cyclic_permutation>_ from a sequence of
unique positive integers.  If p = Permutation.cycle(*cyc), then
p(cyc) == cyc, p(cyc) == cyc, etc., and
p(cyc[-1]) == cyc, with p returning all other values
unchanged.

Permutation.cycle() (with no arguments) evaluates to the identity
permutation.

:param cyc: zero or more unique positive integers
:return: the permutation represented by the given cycle
:raises ValueError:
- if cyc contains a value less than 1
- if cyc contains the same value more than once
"""
cyc = list(cyc)
mapping = {}
maxVal = 0
for (i,v) in enumerate(cyc):
if v < 1:
raise ValueError('values must be positive')
if v in mapping:
raise ValueError('{} appears more than once in cycle'.format(v))
mapping[v] = cyc[i+1] if i < len(cyc)-1 else cyc
if v > maxVal:
maxVal = v
return cls(*(mapping.get(i,i) for i in range(1, maxVal+1)))

[docs]    @classmethod
def from_cycles(cls, *cycles):
"""
Construct a Permutation from zero or more cyclic permutations.  Each
element of cycles is converted to a Permutation with cycle, and
the results (which need not be disjoint) are multiplied together.
Permutation.from_cycles() (with no arguments) evaluates to the
identity permutation.

This is the inverse of to_cycles.

:param cycles: zero or more iterables of unique positive integers
:return: the Permutation represented by the product of the cycles
:raises ValueError:
- if any cycle contains a value less than 1
- if any cycle contains the same value more than once
"""
return reduce(operator.mul, starmap(cls.cycle, cycles), cls())

[docs]    def isdisjoint(self, other):
"""
Returns True iff the permutation and other are disjoint, i.e.,
iff they do not permute any of the same integers

:param Permutation other: a permutation to compare against
:rtype: bool
"""
return all(i+1 in (a,b)
for (i,(a,b)) in enumerate(zip(self.__map, other.__map)))

[docs]    def next_permutation(self):
"""
Returns the next Permutation in left Lehmer code
<#permutation.Permutation.left_lehmer>_ order
"""
map2 = list(self.__map)
for i in range(1, len(map2)):
if map2[i] > map2[i-1]:
j = 0
while map2[i] <= map2[j]:
j += 1
map2[i], map2[j] = map2[j], map2[i]
map2[:i] = reversed(map2[:i])
return type(self)(*map2)
d = max(self.degree, 1)
return type(self).cycle(d, d+1)

[docs]    def prev_permutation(self):
"""
Returns the previous Permutation in left Lehmer code
<#permutation.Permutation.left_lehmer>_ order

:raises ValueError: if called on the identity Permutation (which has
no predecessor)
"""
if self.degree < 2:
raise ValueError('cannot decrement identity')
map2 = list(self.__map)
for i in range(1, len(map2)):
if map2[i] < map2[i-1]:
j = 0
while map2[i] >= map2[j]:
j += 1
map2[i], map2[j] = map2[j], map2[i]
map2[:i] = reversed(map2[:i])
return type(self)(*map2)
assert False  # pragma: no cover

[docs]    @classmethod
def group(cls, n):
r"""
Generates all permutations in :math:S_n, the symmetric group of
degree n, i.e., all permutations with degree less than or equal to
n.  The permutations are yielded in ascending order of their left
Lehmer codes <#permutation.Permutation.left_lehmer>_.

:param int n: a nonnegative integer
:return: a generator of all Permutation\ s with degree n or less
:raises ValueError: if n is less than 0
"""
if n < 0:
raise ValueError(n)
# Use a nested function as the actual generator so that the ValueError
# above can be raised immediately:
def sn():
p = cls()
while p.degree <= n:
yield p
p = p.next_permutation()
return sn()

[docs]    def to_image(self, n=None):
"""
Returns a tuple of the results of applying the permutation to the
integers 1 through n, or through degree if n is unspecified.
If v = p.to_image(), then v == p(1), v == p(2), etc.

When the permutation is the identity, to_image called without an
argument returns an empty tuple.

This is the inverse of the constructor.

:param int n: the length of the image to return; defaults to degree
:return: the image of 1 through n under the permutation
:rtype: tuple of ints
:raise ValueError: if n is less than degree
"""
if n is not None and n < self.degree:
raise ValueError(n)
return self.__map + tuple(range(self.degree+1, (n or self.degree)+1))

[docs]    def permute(self, xs):
"""
Reorder the elements of a sequence according to the permutation; each
element at index i is moved to index p(i).

Note that p.permute(range(1, n+1)) == p.inverse().to_image(n) for
all integers n greater than or equal to degree.

:param xs: a sequence of at least degree elements
:return: a permuted sequence
:rtype: tuple
:raise ValueError: if len(xs) is less than degree
"""
xs = list(xs)
if len(xs) < self.degree:
raise ValueError('sequence must have at least degree elements')
out = [None] * len(xs)
for i in range(len(xs)):
out[self(i+1)-1] = xs[i]
return tuple(out)

[docs]    def inversions(self):
"""

Calculate the inversion number_ of the permutation.  This is the
number of pairs of numbers which are in the opposite order after
applying the permutation.  This is also the Kendall tau distance from
the identity permutation.  This is also the sum of the terms in the
Lehmer code when in factorial base.

.. _Inversion number: https://en.wikipedia.org/wiki/Inversion_(discrete_mathematics)#Inversion_number>

:return: the number of inversions in the permutation
:rtype: int
"""
return sum(self.right_inversion_count())

def lcm(x,y):
""" Calculate the least common multiple of x and y """
d = gcd(x,y)
return 0 if d == 0 else abs(x*y) // d

def to_factorial_base(n):
"""
Convert a nonnegative integer to its representation in the factorial
number system <https://en.wikipedia.org/wiki/Factorial_number_system>_
(represented as a list of digits in descending order of place value, not
including the final zero digit sometimes appended for the :math:0! place)
"""
if n < 0:
raise ValueError(n)
if n == 0:
return 
digits = []
i = 1
while n > 0:
digits.append(n % (i+1))
i += 1
n //= i
digits.reverse()
return digits

def from_factorial_base(digits):
""" Inverse of to_factorial_base """
n = 0
base = 1
for i,d in enumerate(reversed(digits), start=1):
if not (0 <= d <= i):
raise ValueError(digits)
n += d * base
base *= i + 1
return n