<s> from __future__ import print_function , division <EOL> import random <EOL> from collections import defaultdict <EOL> from sympy . core import Basic <EOL> from sympy . core . compatibility import is_sequence , reduce , range , as_int <EOL> from sympy . utilities . iterables import ( flatten , has_variety , minlex , <EOL> has_dups , runs ) <EOL> from sympy . polys . polytools import lcm <EOL> from sympy . matrices import zeros <EOL> from mpmath . libmp . libintmath import ifac <EOL> def _af_rmul ( a , b ) : <EOL> """<STR_LIT>""" <EOL> return [ a [ i ] for i in b ] <EOL> def _af_rmuln ( * abc ) : <EOL> """<STR_LIT>""" <EOL> a = abc <EOL> m = len ( a ) <EOL> if m == <NUM_LIT:3> : <EOL> p0 , p1 , p2 = a <EOL> return [ p0 [ p1 [ i ] ] for i in p2 ] <EOL> if m == <NUM_LIT:4> : <EOL> p0 , p1 , p2 , p3 = a <EOL> return [ p0 [ p1 [ p2 [ i ] ] ] for i in p3 ] <EOL> if m == <NUM_LIT:5> : <EOL> p0 , p1 , p2 , p3 , p4 = a <EOL> return [ p0 [ p1 [ p2 [ p3 [ i ] ] ] ] for i in p4 ] <EOL> if m == <NUM_LIT:6> : <EOL> p0 , p1 , p2 , p3 , p4 , p5 = a <EOL> return [ p0 [ p1 [ p2 [ p3 [ p4 [ i ] ] ] ] ] for i in p5 ] <EOL> if m == <NUM_LIT:7> : <EOL> p0 , p1 , p2 , p3 , p4 , p5 , p6 = a <EOL> return [ p0 [ p1 [ p2 [ p3 [ p4 [ p5 [ i ] ] ] ] ] ] for i in p6 ] <EOL> if m == <NUM_LIT:8> : <EOL> p0 , p1 , p2 , p3 , p4 , p5 , p6 , p7 = a <EOL> return [ p0 [ p1 [ p2 [ p3 [ p4 [ p5 [ p6 [ i ] ] ] ] ] ] ] for i in p7 ] <EOL> if m == <NUM_LIT:1> : <EOL> return a [ <NUM_LIT:0> ] [ : ] <EOL> if m == <NUM_LIT:2> : <EOL> a , b = a <EOL> return [ a [ i ] for i in b ] <EOL> if m == <NUM_LIT:0> : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> p0 = _af_rmuln ( * a [ : m // <NUM_LIT:2> ] ) <EOL> p1 = _af_rmuln ( * a [ m // <NUM_LIT:2> : ] ) <EOL> return [ p0 [ i ] for i in p1 ] <EOL> def _af_parity ( pi ) : <EOL> """<STR_LIT>""" <EOL> n = len ( pi ) <EOL> a = [ <NUM_LIT:0> ] * n <EOL> c = <NUM_LIT:0> <EOL> for j in range ( n ) : <EOL> if a [ j ] == <NUM_LIT:0> : <EOL> c += <NUM_LIT:1> <EOL> a [ j ] = <NUM_LIT:1> <EOL> i = j <EOL> while pi [ i ] != j : <EOL> i = pi [ i ] <EOL> a [ i ] = <NUM_LIT:1> <EOL> return ( n - c ) % <NUM_LIT:2> <EOL> def _af_invert ( a ) : <EOL> """<STR_LIT>""" <EOL> inv_form = [ <NUM_LIT:0> ] * len ( a ) <EOL> for i , ai in enumerate ( a ) : <EOL> inv_form [ ai ] = i <EOL> return inv_form <EOL> def _af_pow ( a , n ) : <EOL> """<STR_LIT>""" <EOL> if n == <NUM_LIT:0> : <EOL> return list ( range ( len ( a ) ) ) <EOL> if n < <NUM_LIT:0> : <EOL> return _af_pow ( _af_invert ( a ) , - n ) <EOL> if n == <NUM_LIT:1> : <EOL> return a [ : ] <EOL> elif n == <NUM_LIT:2> : <EOL> b = [ a [ i ] for i in a ] <EOL> elif n == <NUM_LIT:3> : <EOL> b = [ a [ a [ i ] ] for i in a ] <EOL> elif n == <NUM_LIT:4> : <EOL> b = [ a [ a [ a [ i ] ] ] for i in a ] <EOL> else : <EOL> b = list ( range ( len ( a ) ) ) <EOL> while <NUM_LIT:1> : <EOL> if n & <NUM_LIT:1> : <EOL> b = [ b [ i ] for i in a ] <EOL> n -= <NUM_LIT:1> <EOL> if not n : <EOL> break <EOL> if n % <NUM_LIT:4> == <NUM_LIT:0> : <EOL> a = [ a [ a [ a [ i ] ] ] for i in a ] <EOL> n = n // <NUM_LIT:4> <EOL> elif n % <NUM_LIT:2> == <NUM_LIT:0> : <EOL> a = [ a [ i ] for i in a ] <EOL> n = n // <NUM_LIT:2> <EOL> return b <EOL> def _af_commutes_with ( a , b ) : <EOL> """<STR_LIT>""" <EOL> return not any ( a [ b [ i ] ] != b [ a [ i ] ] for i in range ( len ( a ) - <NUM_LIT:1> ) ) <EOL> class Cycle ( dict ) : <EOL> """<STR_LIT>""" <EOL> def __missing__ ( self , arg ) : <EOL> """<STR_LIT>""" <EOL> arg = as_int ( arg ) <EOL> self [ arg ] = arg <EOL> return arg <EOL> def __iter__ ( self ) : <EOL> for i in self . list ( ) : <EOL> yield i <EOL> def __call__ ( self , * other ) : <EOL> """<STR_LIT>""" <EOL> rv = Cycle ( * other ) <EOL> for k , v in zip ( list ( self . keys ( ) ) , [ rv [ self [ k ] ] for k in self . keys ( ) ] ) : <EOL> rv [ k ] = v <EOL> return rv <EOL> def list ( self , size = None ) : <EOL> """<STR_LIT>""" <EOL> if not self and size is None : <EOL> raise ValueError ( '<STR_LIT>' ) <EOL> if size is not None : <EOL> big = max ( [ i for i in self . keys ( ) if self [ i ] != i ] + [ <NUM_LIT:0> ] ) <EOL> size = max ( size , big + <NUM_LIT:1> ) <EOL> else : <EOL> size = self . size <EOL> return [ self [ i ] for i in range ( size ) ] <EOL> def __repr__ ( self ) : <EOL> """<STR_LIT>""" <EOL> if not self : <EOL> return '<STR_LIT>' <EOL> cycles = Permutation ( self ) . cyclic_form <EOL> s = '<STR_LIT>' . join ( str ( tuple ( c ) ) for c in cycles ) <EOL> big = self . size - <NUM_LIT:1> <EOL> if not any ( i == big for c in cycles for i in c ) : <EOL> s += '<STR_LIT>' % big <EOL> return '<STR_LIT>' % s <EOL> def __str__ ( self ) : <EOL> """<STR_LIT>""" <EOL> if not self : <EOL> return '<STR_LIT>' <EOL> cycles = Permutation ( self ) . cyclic_form <EOL> s = '<STR_LIT>' . join ( str ( tuple ( c ) ) for c in cycles ) <EOL> big = self . size - <NUM_LIT:1> <EOL> if not any ( i == big for c in cycles for i in c ) : <EOL> s += '<STR_LIT>' % big <EOL> s = s . replace ( '<STR_LIT:U+002C>' , '<STR_LIT>' ) <EOL> return s <EOL> def __init__ ( self , * args ) : <EOL> """<STR_LIT>""" <EOL> if not args : <EOL> return <EOL> if len ( args ) == <NUM_LIT:1> : <EOL> if isinstance ( args [ <NUM_LIT:0> ] , Permutation ) : <EOL> for c in args [ <NUM_LIT:0> ] . cyclic_form : <EOL> self . update ( self ( * c ) ) <EOL> return <EOL> elif isinstance ( args [ <NUM_LIT:0> ] , Cycle ) : <EOL> for k , v in args [ <NUM_LIT:0> ] . items ( ) : <EOL> self [ k ] = v <EOL> return <EOL> args = [ as_int ( a ) for a in args ] <EOL> if any ( i < <NUM_LIT:0> for i in args ) : <EOL> raise ValueError ( '<STR_LIT>' ) <EOL> if has_dups ( args ) : <EOL> raise ValueError ( '<STR_LIT>' ) <EOL> for i in range ( - len ( args ) , <NUM_LIT:0> ) : <EOL> self [ args [ i ] ] = args [ i + <NUM_LIT:1> ] <EOL> @ property <EOL> def size ( self ) : <EOL> if not self : <EOL> return <NUM_LIT:0> <EOL> return max ( self . keys ( ) ) + <NUM_LIT:1> <EOL> def copy ( self ) : <EOL> return Cycle ( self ) <EOL> class Permutation ( Basic ) : <EOL> """<STR_LIT>""" <EOL> is_Permutation = True <EOL> _array_form = None <EOL> _cyclic_form = None <EOL> _cycle_structure = None <EOL> _size = None <EOL> _rank = None <EOL> def __new__ ( cls , * args , ** kwargs ) : <EOL> """<STR_LIT>""" <EOL> size = kwargs . pop ( '<STR_LIT:size>' , None ) <EOL> if size is not None : <EOL> size = int ( size ) <EOL> ok = True <EOL> if not args : <EOL> return _af_new ( list ( range ( size or <NUM_LIT:0> ) ) ) <EOL> elif len ( args ) > <NUM_LIT:1> : <EOL> return _af_new ( Cycle ( * args ) . list ( size ) ) <EOL> if len ( args ) == <NUM_LIT:1> : <EOL> a = args [ <NUM_LIT:0> ] <EOL> if isinstance ( a , Perm ) : <EOL> if size is None or size == a . size : <EOL> return a <EOL> return Perm ( a . array_form , size = size ) <EOL> if isinstance ( a , Cycle ) : <EOL> return _af_new ( a . list ( size ) ) <EOL> if not is_sequence ( a ) : <EOL> return _af_new ( list ( range ( a + <NUM_LIT:1> ) ) ) <EOL> if has_variety ( is_sequence ( ai ) for ai in a ) : <EOL> ok = False <EOL> else : <EOL> ok = False <EOL> if not ok : <EOL> raise ValueError ( "<STR_LIT>" <EOL> "<STR_LIT>" ) <EOL> args = list ( args [ <NUM_LIT:0> ] ) <EOL> is_cycle = args and is_sequence ( args [ <NUM_LIT:0> ] ) <EOL> if is_cycle : <EOL> args = [ [ int ( i ) for i in c ] for c in args ] <EOL> else : <EOL> args = [ int ( i ) for i in args ] <EOL> temp = flatten ( args ) <EOL> if has_dups ( temp ) : <EOL> if is_cycle : <EOL> raise ValueError ( '<STR_LIT>' <EOL> '<STR_LIT>' % '<STR_LIT>' . join ( [ str ( tuple ( c ) ) for c in args ] ) ) <EOL> else : <EOL> raise ValueError ( '<STR_LIT>' ) <EOL> temp = set ( temp ) <EOL> if not is_cycle and any ( i not in temp for i in range ( len ( temp ) ) ) : <EOL> raise ValueError ( "<STR_LIT>" % <EOL> max ( temp ) ) <EOL> if is_cycle : <EOL> c = Cycle ( ) <EOL> for ci in args : <EOL> c = c ( * ci ) <EOL> aform = c . list ( ) <EOL> else : <EOL> aform = list ( args ) <EOL> if size and size > len ( aform ) : <EOL> aform . extend ( list ( range ( len ( aform ) , size ) ) ) <EOL> size = len ( aform ) <EOL> obj = Basic . __new__ ( cls , aform ) <EOL> obj . _array_form = aform <EOL> obj . _size = size <EOL> return obj <EOL> @ staticmethod <EOL> def _af_new ( perm ) : <EOL> """<STR_LIT>""" <EOL> p = Basic . __new__ ( Perm , perm ) <EOL> p . _array_form = perm <EOL> p . _size = len ( perm ) <EOL> return p <EOL> def _hashable_content ( self ) : <EOL> return tuple ( self . array_form ) <EOL> @ property <EOL> def array_form ( self ) : <EOL> """<STR_LIT>""" <EOL> return self . _array_form [ : ] <EOL> def __repr__ ( self ) : <EOL> from sympy . combinatorics . permutations import Permutation , Cycle <EOL> if Permutation . print_cyclic : <EOL> if not self . size : <EOL> return '<STR_LIT>' <EOL> s = Cycle ( self ) ( self . size - <NUM_LIT:1> ) . __repr__ ( ) [ len ( '<STR_LIT>' ) : ] <EOL> last = s . rfind ( '<STR_LIT:(>' ) <EOL> if not last == <NUM_LIT:0> and '<STR_LIT:U+002C>' not in s [ last : ] : <EOL> s = s [ last : ] + s [ : last ] <EOL> return '<STR_LIT>' % s <EOL> else : <EOL> s = self . support ( ) <EOL> if not s : <EOL> if self . size < <NUM_LIT:5> : <EOL> return '<STR_LIT>' % str ( self . array_form ) <EOL> return '<STR_LIT>' % self . size <EOL> trim = str ( self . array_form [ : s [ - <NUM_LIT:1> ] + <NUM_LIT:1> ] ) + '<STR_LIT>' % self . size <EOL> use = full = str ( self . array_form ) <EOL> if len ( trim ) < len ( full ) : <EOL> use = trim <EOL> return '<STR_LIT>' % use <EOL> def list ( self , size = None ) : <EOL> """<STR_LIT>""" <EOL> if not self and size is None : <EOL> raise ValueError ( '<STR_LIT>' ) <EOL> rv = self . array_form <EOL> if size is not None : <EOL> if size > self . size : <EOL> rv . extend ( list ( range ( self . size , size ) ) ) <EOL> else : <EOL> i = self . size - <NUM_LIT:1> <EOL> while rv : <EOL> if rv [ - <NUM_LIT:1> ] != i : <EOL> break <EOL> rv . pop ( ) <EOL> i -= <NUM_LIT:1> <EOL> return rv <EOL> @ property <EOL> def cyclic_form ( self ) : <EOL> """<STR_LIT>""" <EOL> if self . _cyclic_form is not None : <EOL> return list ( self . _cyclic_form ) <EOL> array_form = self . array_form <EOL> unchecked = [ True ] * len ( array_form ) <EOL> cyclic_form = [ ] <EOL> for i in range ( len ( array_form ) ) : <EOL> if unchecked [ i ] : <EOL> cycle = [ ] <EOL> cycle . append ( i ) <EOL> unchecked [ i ] = False <EOL> j = i <EOL> while unchecked [ array_form [ j ] ] : <EOL> j = array_form [ j ] <EOL> cycle . append ( j ) <EOL> unchecked [ j ] = False <EOL> if len ( cycle ) > <NUM_LIT:1> : <EOL> cyclic_form . append ( cycle ) <EOL> assert cycle == list ( minlex ( cycle , is_set = True ) ) <EOL> cyclic_form . sort ( ) <EOL> self . _cyclic_form = cyclic_form [ : ] <EOL> return cyclic_form <EOL> @ property <EOL> def full_cyclic_form ( self ) : <EOL> """<STR_LIT>""" <EOL> need = set ( range ( self . size ) ) - set ( flatten ( self . cyclic_form ) ) <EOL> rv = self . cyclic_form <EOL> rv . extend ( [ [ i ] for i in need ] ) <EOL> rv . sort ( ) <EOL> return rv <EOL> @ property <EOL> def size ( self ) : <EOL> """<STR_LIT>""" <EOL> return self . _size <EOL> def support ( self ) : <EOL> """<STR_LIT>""" <EOL> a = self . array_form <EOL> return [ i for i , e in enumerate ( a ) if a [ i ] != i ] <EOL> def __add__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> rank = ( self . rank ( ) + other ) % self . cardinality <EOL> rv = Perm . unrank_lex ( self . size , rank ) <EOL> rv . _rank = rank <EOL> return rv <EOL> def __sub__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> return self . __add__ ( - other ) <EOL> @ staticmethod <EOL> def rmul ( * args ) : <EOL> """<STR_LIT>""" <EOL> rv = args [ <NUM_LIT:0> ] <EOL> for i in range ( <NUM_LIT:1> , len ( args ) ) : <EOL> rv = args [ i ] * rv <EOL> return rv <EOL> @ staticmethod <EOL> def rmul_with_af ( * args ) : <EOL> """<STR_LIT>""" <EOL> a = [ x . _array_form for x in args ] <EOL> rv = _af_new ( _af_rmuln ( * a ) ) <EOL> return rv <EOL> def mul_inv ( self , other ) : <EOL> """<STR_LIT>""" <EOL> a = _af_invert ( self . _array_form ) <EOL> b = other . _array_form <EOL> return _af_new ( _af_rmul ( a , b ) ) <EOL> def __rmul__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> return Perm ( other ) * self <EOL> def __mul__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> a = self . array_form <EOL> b = other . array_form <EOL> if not b : <EOL> perm = a <EOL> else : <EOL> b . extend ( list ( range ( len ( b ) , len ( a ) ) ) ) <EOL> perm = [ b [ i ] for i in a ] + b [ len ( a ) : ] <EOL> return _af_new ( perm ) <EOL> def commutes_with ( self , other ) : <EOL> """<STR_LIT>""" <EOL> a = self . array_form <EOL> b = other . array_form <EOL> return _af_commutes_with ( a , b ) <EOL> def __pow__ ( self , n ) : <EOL> """<STR_LIT>""" <EOL> if type ( n ) == Perm : <EOL> raise NotImplementedError ( <EOL> '<STR_LIT>' ) <EOL> n = int ( n ) <EOL> return _af_new ( _af_pow ( self . array_form , n ) ) <EOL> def __rxor__ ( self , i ) : <EOL> """<STR_LIT>""" <EOL> if int ( i ) == i : <EOL> return self ( i ) <EOL> else : <EOL> raise NotImplementedError ( <EOL> "<STR_LIT>" % i ) <EOL> def __xor__ ( self , h ) : <EOL> """<STR_LIT>""" <EOL> if self . size != h . size : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> a = [ None ] * self . size <EOL> h = h . _array_form <EOL> p = self . _array_form <EOL> for i in range ( self . size ) : <EOL> a [ h [ i ] ] = h [ p [ i ] ] <EOL> return _af_new ( a ) <EOL> def transpositions ( self ) : <EOL> """<STR_LIT>""" <EOL> a = self . cyclic_form <EOL> res = [ ] <EOL> for x in a : <EOL> nx = len ( x ) <EOL> if nx == <NUM_LIT:2> : <EOL> res . append ( tuple ( x ) ) <EOL> elif nx > <NUM_LIT:2> : <EOL> first = x [ <NUM_LIT:0> ] <EOL> for y in x [ nx - <NUM_LIT:1> : <NUM_LIT:0> : - <NUM_LIT:1> ] : <EOL> res . append ( ( first , y ) ) <EOL> return res <EOL> @ classmethod <EOL> def from_sequence ( self , i , key = None ) : <EOL> """<STR_LIT>""" <EOL> ic = list ( zip ( i , list ( range ( len ( i ) ) ) ) ) <EOL> if key : <EOL> ic . sort ( key = lambda x : key ( x [ <NUM_LIT:0> ] ) ) <EOL> else : <EOL> ic . sort ( ) <EOL> return ~ Permutation ( [ i [ <NUM_LIT:1> ] for i in ic ] ) <EOL> def __invert__ ( self ) : <EOL> """<STR_LIT>""" <EOL> return _af_new ( _af_invert ( self . _array_form ) ) <EOL> def __iter__ ( self ) : <EOL> """<STR_LIT>""" <EOL> for i in self . array_form : <EOL> yield i <EOL> def __call__ ( self , * i ) : <EOL> """<STR_LIT>""" <EOL> if len ( i ) == <NUM_LIT:1> : <EOL> i = i [ <NUM_LIT:0> ] <EOL> try : <EOL> return self . _array_form [ i ] <EOL> except TypeError : <EOL> try : <EOL> return [ i [ j ] for j in self . _array_form ] <EOL> except Exception : <EOL> raise TypeError ( '<STR_LIT>' ) <EOL> else : <EOL> return self * Permutation ( Cycle ( * i ) , size = self . size ) <EOL> def atoms ( self ) : <EOL> """<STR_LIT>""" <EOL> return set ( self . array_form ) <EOL> def next_lex ( self ) : <EOL> """<STR_LIT>""" <EOL> perm = self . array_form [ : ] <EOL> n = len ( perm ) <EOL> i = n - <NUM_LIT:2> <EOL> while perm [ i + <NUM_LIT:1> ] < perm [ i ] : <EOL> i -= <NUM_LIT:1> <EOL> if i == - <NUM_LIT:1> : <EOL> return None <EOL> else : <EOL> j = n - <NUM_LIT:1> <EOL> while perm [ j ] < perm [ i ] : <EOL> j -= <NUM_LIT:1> <EOL> perm [ j ] , perm [ i ] = perm [ i ] , perm [ j ] <EOL> i += <NUM_LIT:1> <EOL> j = n - <NUM_LIT:1> <EOL> while i < j : <EOL> perm [ j ] , perm [ i ] = perm [ i ] , perm [ j ] <EOL> i += <NUM_LIT:1> <EOL> j -= <NUM_LIT:1> <EOL> return _af_new ( perm ) <EOL> @ classmethod <EOL> def unrank_nonlex ( self , n , r ) : <EOL> """<STR_LIT>""" <EOL> def _unrank1 ( n , r , a ) : <EOL> if n > <NUM_LIT:0> : <EOL> a [ n - <NUM_LIT:1> ] , a [ r % n ] = a [ r % n ] , a [ n - <NUM_LIT:1> ] <EOL> _unrank1 ( n - <NUM_LIT:1> , r // n , a ) <EOL> id_perm = list ( range ( n ) ) <EOL> n = int ( n ) <EOL> r = r % ifac ( n ) <EOL> _unrank1 ( n , r , id_perm ) <EOL> return _af_new ( id_perm ) <EOL> def rank_nonlex ( self , inv_perm = None ) : <EOL> """<STR_LIT>""" <EOL> def _rank1 ( n , perm , inv_perm ) : <EOL> if n == <NUM_LIT:1> : <EOL> return <NUM_LIT:0> <EOL> s = perm [ n - <NUM_LIT:1> ] <EOL> t = inv_perm [ n - <NUM_LIT:1> ] <EOL> perm [ n - <NUM_LIT:1> ] , perm [ t ] = perm [ t ] , s <EOL> inv_perm [ n - <NUM_LIT:1> ] , inv_perm [ s ] = inv_perm [ s ] , t <EOL> return s + n * _rank1 ( n - <NUM_LIT:1> , perm , inv_perm ) <EOL> if inv_perm is None : <EOL> inv_perm = ( ~ self ) . array_form <EOL> if not inv_perm : <EOL> return <NUM_LIT:0> <EOL> perm = self . array_form [ : ] <EOL> r = _rank1 ( len ( perm ) , perm , inv_perm ) <EOL> return r <EOL> def next_nonlex ( self ) : <EOL> """<STR_LIT>""" <EOL> r = self . rank_nonlex ( ) <EOL> if r == ifac ( self . size ) - <NUM_LIT:1> : <EOL> return None <EOL> return Perm . unrank_nonlex ( self . size , r + <NUM_LIT:1> ) <EOL> def rank ( self ) : <EOL> """<STR_LIT>""" <EOL> if not self . _rank is None : <EOL> return self . _rank <EOL> rank = <NUM_LIT:0> <EOL> rho = self . array_form [ : ] <EOL> n = self . size - <NUM_LIT:1> <EOL> size = n + <NUM_LIT:1> <EOL> psize = int ( ifac ( n ) ) <EOL> for j in range ( size - <NUM_LIT:1> ) : <EOL> rank += rho [ j ] * psize <EOL> for i in range ( j + <NUM_LIT:1> , size ) : <EOL> if rho [ i ] > rho [ j ] : <EOL> rho [ i ] -= <NUM_LIT:1> <EOL> psize //= n <EOL> n -= <NUM_LIT:1> <EOL> self . _rank = rank <EOL> return rank <EOL> @ property <EOL> def cardinality ( self ) : <EOL> """<STR_LIT>""" <EOL> return int ( ifac ( self . size ) ) <EOL> def parity ( self ) : <EOL> """<STR_LIT>""" <EOL> if self . _cyclic_form is not None : <EOL> return ( self . size - self . cycles ) % <NUM_LIT:2> <EOL> return _af_parity ( self . array_form ) <EOL> @ property <EOL> def is_even ( self ) : <EOL> """<STR_LIT>""" <EOL> return not self . is_odd <EOL> @ property <EOL> def is_odd ( self ) : <EOL> """<STR_LIT>""" <EOL> return bool ( self . parity ( ) % <NUM_LIT:2> ) <EOL> @ property <EOL> def is_Singleton ( self ) : <EOL> """<STR_LIT>""" <EOL> return self . size == <NUM_LIT:1> <EOL> @ property <EOL> def is_Empty ( self ) : <EOL> """<STR_LIT>""" <EOL> return self . size == <NUM_LIT:0> <EOL> @ property <EOL> def is_Identity ( self ) : <EOL> """<STR_LIT>""" <EOL> af = self . array_form <EOL> return not af or all ( i == af [ i ] for i in range ( self . size ) ) <EOL> def ascents ( self ) : <EOL> """<STR_LIT>""" <EOL> a = self . array_form <EOL> pos = [ i for i in range ( len ( a ) - <NUM_LIT:1> ) if a [ i ] < a [ i + <NUM_LIT:1> ] ] <EOL> return pos <EOL> def descents ( self ) : <EOL> """<STR_LIT>""" <EOL> a = self . array_form <EOL> pos = [ i for i in range ( len ( a ) - <NUM_LIT:1> ) if a [ i ] > a [ i + <NUM_LIT:1> ] ] <EOL> return pos <EOL> def max ( self ) : <EOL> """<STR_LIT>""" <EOL> max = <NUM_LIT:0> <EOL> a = self . array_form <EOL> for i in range ( len ( a ) ) : <EOL> if a [ i ] != i and a [ i ] > max : <EOL> max = a [ i ] <EOL> return max <EOL> def min ( self ) : <EOL> """<STR_LIT>""" <EOL> a = self . array_form <EOL> min = len ( a ) <EOL> for i in range ( len ( a ) ) : <EOL> if a [ i ] != i and a [ i ] < min : <EOL> min = a [ i ] <EOL> return min <EOL> def inversions ( self ) : <EOL> """<STR_LIT>""" <EOL> inversions = <NUM_LIT:0> <EOL> a = self . array_form <EOL> n = len ( a ) <EOL> if n < <NUM_LIT> : <EOL> for i in range ( n - <NUM_LIT:1> ) : <EOL> b = a [ i ] <EOL> for c in a [ i + <NUM_LIT:1> : ] : <EOL> if b > c : <EOL> inversions += <NUM_LIT:1> <EOL> else : <EOL> k = <NUM_LIT:1> <EOL> right = <NUM_LIT:0> <EOL> arr = a [ : ] <EOL> temp = a [ : ] <EOL> while k < n : <EOL> i = <NUM_LIT:0> <EOL> while i + k < n : <EOL> right = i + k * <NUM_LIT:2> - <NUM_LIT:1> <EOL> if right >= n : <EOL> right = n - <NUM_LIT:1> <EOL> inversions += _merge ( arr , temp , i , i + k , right ) <EOL> i = i + k * <NUM_LIT:2> <EOL> k = k * <NUM_LIT:2> <EOL> return inversions <EOL> def commutator ( self , x ) : <EOL> """<STR_LIT>""" <EOL> a = self . array_form <EOL> b = x . array_form <EOL> n = len ( a ) <EOL> if len ( b ) != n : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> inva = [ None ] * n <EOL> for i in range ( n ) : <EOL> inva [ a [ i ] ] = i <EOL> invb = [ None ] * n <EOL> for i in range ( n ) : <EOL> invb [ b [ i ] ] = i <EOL> return _af_new ( [ a [ b [ inva [ i ] ] ] for i in invb ] ) <EOL> def signature ( self ) : <EOL> """<STR_LIT>""" <EOL> if self . is_even : <EOL> return <NUM_LIT:1> <EOL> return - <NUM_LIT:1> <EOL> def order ( self ) : <EOL> """<STR_LIT>""" <EOL> return reduce ( lcm , [ len ( cycle ) for cycle in self . cyclic_form ] , <NUM_LIT:1> ) <EOL> def length ( self ) : <EOL> """<STR_LIT>""" <EOL> return len ( self . support ( ) ) <EOL> @ property <EOL> def cycle_structure ( self ) : <EOL> """<STR_LIT>""" <EOL> if self . _cycle_structure : <EOL> rv = self . _cycle_structure <EOL> else : <EOL> rv = defaultdict ( int ) <EOL> singletons = self . size <EOL> for c in self . cyclic_form : <EOL> rv [ len ( c ) ] += <NUM_LIT:1> <EOL> singletons -= len ( c ) <EOL> if singletons : <EOL> rv [ <NUM_LIT:1> ] = singletons <EOL> self . _cycle_structure = rv <EOL> return dict ( rv ) <EOL> @ property <EOL> def cycles ( self ) : <EOL> """<STR_LIT>""" <EOL> return len ( self . full_cyclic_form ) <EOL> def index ( self ) : <EOL> """<STR_LIT>""" <EOL> a = self . array_form <EOL> return sum ( [ j for j in range ( len ( a ) - <NUM_LIT:1> ) if a [ j ] > a [ j + <NUM_LIT:1> ] ] ) <EOL> def runs ( self ) : <EOL> """<STR_LIT>""" <EOL> return runs ( self . array_form ) <EOL> def inversion_vector ( self ) : <EOL> """<STR_LIT>""" <EOL> self_array_form = self . array_form <EOL> n = len ( self_array_form ) <EOL> inversion_vector = [ <NUM_LIT:0> ] * ( n - <NUM_LIT:1> ) <EOL> for i in range ( n - <NUM_LIT:1> ) : <EOL> val = <NUM_LIT:0> <EOL> for j in range ( i + <NUM_LIT:1> , n ) : <EOL> if self_array_form [ j ] < self_array_form [ i ] : <EOL> val += <NUM_LIT:1> <EOL> inversion_vector [ i ] = val <EOL> return inversion_vector <EOL> def rank_trotterjohnson ( self ) : <EOL> """<STR_LIT>""" <EOL> if self . array_form == [ ] or self . is_Identity : <EOL> return <NUM_LIT:0> <EOL> if self . array_form == [ <NUM_LIT:1> , <NUM_LIT:0> ] : <EOL> return <NUM_LIT:1> <EOL> perm = self . array_form <EOL> n = self . size <EOL> rank = <NUM_LIT:0> <EOL> for j in range ( <NUM_LIT:1> , n ) : <EOL> k = <NUM_LIT:1> <EOL> i = <NUM_LIT:0> <EOL> while perm [ i ] != j : <EOL> if perm [ i ] < j : <EOL> k += <NUM_LIT:1> <EOL> i += <NUM_LIT:1> <EOL> j1 = j + <NUM_LIT:1> <EOL> if rank % <NUM_LIT:2> == <NUM_LIT:0> : <EOL> rank = j1 * rank + j1 - k <EOL> else : <EOL> rank = j1 * rank + k - <NUM_LIT:1> <EOL> return rank <EOL> @ classmethod <EOL> def unrank_trotterjohnson ( self , size , rank ) : <EOL> """<STR_LIT>""" <EOL> perm = [ <NUM_LIT:0> ] * size <EOL> r2 = <NUM_LIT:0> <EOL> n = ifac ( size ) <EOL> pj = <NUM_LIT:1> <EOL> for j in range ( <NUM_LIT:2> , size + <NUM_LIT:1> ) : <EOL> pj *= j <EOL> r1 = ( rank * pj ) // n <EOL> k = r1 - j * r2 <EOL> if r2 % <NUM_LIT:2> == <NUM_LIT:0> : <EOL> for i in range ( j - <NUM_LIT:1> , j - k - <NUM_LIT:1> , - <NUM_LIT:1> ) : <EOL> perm [ i ] = perm [ i - <NUM_LIT:1> ] <EOL> perm [ j - k - <NUM_LIT:1> ] = j - <NUM_LIT:1> <EOL> else : <EOL> for i in range ( j - <NUM_LIT:1> , k , - <NUM_LIT:1> ) : <EOL> perm [ i ] = perm [ i - <NUM_LIT:1> ] <EOL> perm [ k ] = j - <NUM_LIT:1> <EOL> r2 = r1 <EOL> return _af_new ( perm ) <EOL> def next_trotterjohnson ( self ) : <EOL> """<STR_LIT>""" <EOL> pi = self . array_form [ : ] <EOL> n = len ( pi ) <EOL> st = <NUM_LIT:0> <EOL> rho = pi [ : ] <EOL> done = False <EOL> m = n - <NUM_LIT:1> <EOL> while m > <NUM_LIT:0> and not done : <EOL> d = rho . index ( m ) <EOL> for i in range ( d , m ) : <EOL> rho [ i ] = rho [ i + <NUM_LIT:1> ] <EOL> par = _af_parity ( rho [ : m ] ) <EOL> if par == <NUM_LIT:1> : <EOL> if d == m : <EOL> m -= <NUM_LIT:1> <EOL> else : <EOL> pi [ st + d ] , pi [ st + d + <NUM_LIT:1> ] = pi [ st + d + <NUM_LIT:1> ] , pi [ st + d ] <EOL> done = True <EOL> else : <EOL> if d == <NUM_LIT:0> : <EOL> m -= <NUM_LIT:1> <EOL> st += <NUM_LIT:1> <EOL> else : <EOL> pi [ st + d ] , pi [ st + d - <NUM_LIT:1> ] = pi [ st + d - <NUM_LIT:1> ] , pi [ st + d ] <EOL> done = True <EOL> if m == <NUM_LIT:0> : <EOL> return None <EOL> return _af_new ( pi ) <EOL> def get_precedence_matrix ( self ) : <EOL> """<STR_LIT>""" <EOL> m = zeros ( self . size ) <EOL> perm = self . array_form <EOL> for i in range ( m . rows ) : <EOL> for j in range ( i + <NUM_LIT:1> , m . cols ) : <EOL> m [ perm [ i ] , perm [ j ] ] = <NUM_LIT:1> <EOL> return m <EOL> def get_precedence_distance ( self , other ) : <EOL> """<STR_LIT>""" <EOL> if self . size != other . size : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> self_prec_mat = self . get_precedence_matrix ( ) <EOL> other_prec_mat = other . get_precedence_matrix ( ) <EOL> n_prec = <NUM_LIT:0> <EOL> for i in range ( self . size ) : <EOL> for j in range ( self . size ) : <EOL> if i == j : <EOL> continue <EOL> if self_prec_mat [ i , j ] * other_prec_mat [ i , j ] == <NUM_LIT:1> : <EOL> n_prec += <NUM_LIT:1> <EOL> d = self . size * ( self . size - <NUM_LIT:1> ) // <NUM_LIT:2> - n_prec <EOL> return d <EOL> def get_adjacency_matrix ( self ) : <EOL> """<STR_LIT>""" <EOL> m = zeros ( self . size ) <EOL> perm = self . array_form <EOL> for i in range ( self . size - <NUM_LIT:1> ) : <EOL> m [ perm [ i ] , perm [ i + <NUM_LIT:1> ] ] = <NUM_LIT:1> <EOL> return m <EOL> def get_adjacency_distance ( self , other ) : <EOL> """<STR_LIT>""" <EOL> if self . size != other . size : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> self_adj_mat = self . get_adjacency_matrix ( ) <EOL> other_adj_mat = other . get_adjacency_matrix ( ) <EOL> n_adj = <NUM_LIT:0> <EOL> for i in range ( self . size ) : <EOL> for j in range ( self . size ) : <EOL> if i == j : <EOL> continue <EOL> if self_adj_mat [ i , j ] * other_adj_mat [ i , j ] == <NUM_LIT:1> : <EOL> n_adj += <NUM_LIT:1> <EOL> d = self . size - n_adj - <NUM_LIT:1> <EOL> return d <EOL> def get_positional_distance ( self , other ) : <EOL> """<STR_LIT>""" <EOL> a = self . array_form <EOL> b = other . array_form <EOL> if len ( a ) != len ( b ) : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> return sum ( [ abs ( a [ i ] - b [ i ] ) for i in range ( len ( a ) ) ] ) <EOL> @ classmethod <EOL> def josephus ( self , m , n , s = <NUM_LIT:1> ) : <EOL> """<STR_LIT>""" <EOL> from collections import deque <EOL> m -= <NUM_LIT:1> <EOL> Q = deque ( list ( range ( n ) ) ) <EOL> perm = [ ] <EOL> while len ( Q ) > max ( s , <NUM_LIT:1> ) : <EOL> for dp in range ( m ) : <EOL> Q . append ( Q . popleft ( ) ) <EOL> perm . append ( Q . popleft ( ) ) <EOL> perm . extend ( list ( Q ) ) <EOL> return Perm ( perm ) <EOL> @ classmethod <EOL> def from_inversion_vector ( self , inversion ) : <EOL> """<STR_LIT>""" <EOL> size = len ( inversion ) <EOL> N = list ( range ( size + <NUM_LIT:1> ) ) <EOL> perm = [ ] <EOL> try : <EOL> for k in range ( size ) : <EOL> val = N [ inversion [ k ] ] <EOL> perm . append ( val ) <EOL> N . remove ( val ) <EOL> except IndexError : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> perm . extend ( N ) <EOL> return _af_new ( perm ) <EOL> @ classmethod <EOL> def random ( self , n ) : <EOL> """<STR_LIT>""" <EOL> perm_array = list ( range ( n ) ) <EOL> random . shuffle ( perm_array ) <EOL> return _af_new ( perm_array ) <EOL> @ classmethod <EOL> def unrank_lex ( self , size , rank ) : <EOL> """<STR_LIT>""" <EOL> perm_array = [ <NUM_LIT:0> ] * size <EOL> psize = <NUM_LIT:1> <EOL> for i in range ( size ) : <EOL> new_psize = psize * ( i + <NUM_LIT:1> ) <EOL> d = ( rank % new_psize ) // psize <EOL> rank -= d * psize <EOL> perm_array [ size - i - <NUM_LIT:1> ] = d <EOL> for j in range ( size - i , size ) : <EOL> if perm_array [ j ] > d - <NUM_LIT:1> : <EOL> perm_array [ j ] += <NUM_LIT:1> <EOL> psize = new_psize <EOL> return _af_new ( perm_array ) <EOL> print_cyclic = True <EOL> def _merge ( arr , temp , left , mid , right ) : <EOL> """<STR_LIT>""" <EOL> i = k = left <EOL> j = mid <EOL> inv_count = <NUM_LIT:0> <EOL> while i < mid and j <= right : <EOL> if arr [ i ] < arr [ j ] : <EOL> temp [ k ] = arr [ i ] <EOL> k += <NUM_LIT:1> <EOL> i += <NUM_LIT:1> <EOL> else : <EOL> temp [ k ] = arr [ j ] <EOL> k += <NUM_LIT:1> <EOL> j += <NUM_LIT:1> <EOL> inv_count += ( mid - i ) <EOL> while i < mid : <EOL> temp [ k ] = arr [ i ] <EOL> k += <NUM_LIT:1> <EOL> i += <NUM_LIT:1> <EOL> if j <= right : <EOL> k += right - j + <NUM_LIT:1> <EOL> j += right - j + <NUM_LIT:1> <EOL> arr [ left : k + <NUM_LIT:1> ] = temp [ left : k + <NUM_LIT:1> ] <EOL> else : <EOL> arr [ left : right + <NUM_LIT:1> ] = temp [ left : right + <NUM_LIT:1> ] <EOL> return inv_count <EOL> Perm = Permutation <EOL> _af_new = Perm . _af_new </s>
