## This is the code that accompanies the series of papers A bijective proof of the ASM theorem
## by Ilse Fischer and Matjaz Konvalinka. Part I, II etc. below refer to parts of this series.
## This is work in progress. Contact ilse.fischer@univie.ac.at or matjaz.konvalinka@fmf.uni-lj.si
## for questions and comments.
## (c) Ilse Fischer and Matjaz Konvalinka, 2019

import itertools
import time

## -------------------------------------------------------------
## A signed set is a pair of disjoint finite sets (S0, S1). We implement it is as a 2-tuple
## of lists of tuples. To construct a simple finite set, one can write S = ([(1, 3),(2, 4)], [(5, 3)])
## The following are basic signed set constructions. Most are defined in Part I.
## -------------------------------------------------------------

## sssize(S) computes the size |S| = |S0| - |S1| of a signed set S.
def sssize(S):
    return len(S[0]) - len(S[1])

## ssminus(S) computes -S = (S1, S0) for a signed set S.
def ssminus(S):
    return (S[1], S[0])

## sspm(i)(S) returns S if i is even and -S if i is odd.
def sspm(i):
    return (lambda S: S if i % 2 == 0 else ssminus(S))

## sselements(S) computes the set of elements of a signed set S, i.e. the union of S0 and S1.
def sselements(S):
    return set(S[0] + S[1])

## ssempty() produces the empty signed set.
def ssempty():
    return ([],[])

## ssunion(A) computes the union of a list A of signed sets.
def ssunion(A):
    return (list(itertools.chain.from_iterable([B[0] for B in A])),
            list(itertools.chain.from_iterable([B[1] for B in A])))

## sscartesian(A) computes the cartesian product of a list A of signed sets.
def sscartesian(A):
    if A == []:
        return ([()],[])
    else:
        return (list(itertools.chain.from_iterable([([(s) for s in
                itertools.product(*[A[i][element[i] if i < len(A)-1 else
                (sum(element) % 2)] for i in range(len(A))])])
                 for element in itertools.product(*[[[0,1]]*(len(A)-1)][0])])),
                list(itertools.chain.from_iterable([([(s) for s in itertools.product
                (*[A[i][element[i] if i < len(A)-1 else ((1+sum(element)) % 2)]
                for i in range(len(A))])]) for element in
                itertools.product(*[[[0,1]]*(len(A)-1)][0])])))

## ssdisjointunion(T, phi) computes the disjoint union of signed sets, indexed by a signed set.
## Here phi is the "indexing" function T -> signed sets.
def ssdisjointunion(T, phi):
    return ssunion([ssunion([sscartesian([phi(q), ([q], [])]) for q in T[0]]),
                    ssunion([sscartesian([phi(q), ([], [q])]) for q in T[1]])])

## ssdisjointunion2(S, T) computes the disjoint union of signed sets S and T.
def ssdisjointunion2(S, T):
    return ssdisjointunion(ssinterval(0, 1), lambda x: S if x == 0 else T)

## ssinterval(a, b) gives the the signed interval between a and b.
def ssinterval(a, b):
    if a <= b:
        return ([i for i in range(a, b + 1)], [])
    else:
        return ([], [i for i in range(b + 1, a)])

## GT(l) gives the Gelfand--Tsetlin patterns with a prescribed bottom row l.
def GT(l):
    if len(l) == 1:
        return ([()],[])
    else:
        return ssdisjointunion(sscartesian([ssinterval(l[i],l[i+1]) for i
               in range(len(l)-1)]), lambda x: GT(list(x)))

## AP(n) construct the signed set of arrow patterns of order n.
def AP(n):
    return sscartesian([([1,-1],[0])]*(n*(n-1)//2))

## APlisttoarray(T, n) takes an arrow pattern of order n (which is a list) and returns 
## a function f(i, j) which tells us the entry in position (i, j).
def APlisttoarray(T, n):
    return (lambda i, j: T[((n - j + i) * (n - j + i - 1) // 2) + i - 1])

## AParraytolist is the inverse of APlisttoarray.
def AParraytolist(f, n):
    return tuple([f(j, j + n - i) for i in range(1, n) for j in range(1, i + 1)])

## c is the map defined in Section 5 of Part I.
def c(T, n, i):
    def c2(f, n, i):
        return sum([(1 if f(i, j) <= 0 else 0) for j in range(i + 1, n + 1)]) - sum([(1 if f(j, i) >= 0 else 0) for j in range(1, i)])
    return c2(APlisttoarray(T, n), n, i)

## AR(n) construct the signed set of arrow rows of order n.
def AR(n):
    return sscartesian([([1, -1], [0])]*n)

## SGT(kk) gives the signed set of shifted GT patterns corresponding to kk.
def SGT(kk):
    return ssdisjointunion(AP(len(kk)), lambda T: GT(tuple([kk[i] + c(T,len(kk),i+1) for i in range(len(kk))])))

## showSGT(T, kk) presents the shifted GT pattern in a more readable form.
def showSGT(T,kk):
    n = len(T[1])
    return((tuple(list(T[0]) + [tuple([kk[i] + c(T[1],n,i+1) for i in range(len(kk))])]),[T[1][(i*(i+1)//2):((i+2)*(i+1)//2)] for i in range(n-1)]))

## triangles(kk) produces the set of all triangles with bottom row kk, with each element lying on
## the closed interval between the entries below it.
def triangles(kk):
    if len(kk) == 1:
        return [(kk,)]
    return [tuple(list(u) + [kk]) for s in itertools.product(*([(lambda q: range(min(q), max(q) + 1))([kk[i], kk[i + 1]]) for i in range(len(kk) - 1)])) for u in triangles(s)]

## logical implies
def implies(p,q):
    return not(p) or q

## ismonotone(T) checks if the triangle T is monotone
def ismonotone(T):
    return all([implies(T[i+1][j] <= T[i+1][j+1] == T[i][j], j == i or implies(T[i][j+1] == T[i][j], T[i+1][j+2] < T[i][j])) and 
implies(T[i][j] == T[i+1][j] < T[i+1][j+1], j == 0 or implies(T[i][j-1] == T[i][j], T[i+1][j-1] > T[i][j])) and 
implies(T[i+1][j] > T[i+1][j+1] == T[i][j], j < i and T[i][j+1] == T[i][j]) and
implies(T[i][j] == T[i+1][j] > T[i+1][j+1], j > 0 and T[i][j-1] == T[i][j])
for i in range(len(T)-1) for j in range(i+1)])

## montriang(kk) produces the set of all monotone triangles with bottom row kk.
def montriang(kk):
    return list(filter(ismonotone,triangles(kk)))

## sign(T) computes the sign of the monotone triangle T.
def sign(T):
    return (-1)**([(T[i][j] > T[i][j+1] or (i < len(T)-1 and T[i+1][j] > T[i][j]
        == T[i+1][j+1] == T[i][j+1] > T[i+1][j+2])) for i in range(len(T))
      for j in range(i)].count(True))

## MT(kk) produces the signed set of all monotone triangles with bottom row kk.
def MT(kk):
    A = montriang(kk)
    return (list(filter(lambda T: sign(T) == 1,A)),list(filter(lambda T: sign(T) == -1,A)))

## -------------------------------------------------------------
## The following are basic sijection constructions. Most are defined in Part I or are obvious.
## -------------------------------------------------------------

## sijectionQ(S, phi, T) checks that phi is a sijection between S and T. phi should be defined on
## the disjoint union of S and T, i.e. it accepts entries (s, 0) for s in S and (t, 1) for t in T.
def sijectionQ1(S, phi, T):
    return all([phi(phi(tuple([s,0]))) == tuple([s,0]) for s in S[0] + S[1]])
def sijectionQ2(S, phi, T):
    return all([phi(phi(tuple([t,1]))) == tuple([t,1]) for t in T[0] + T[1]])
def sijectionQ3(S, phi, T):
    return set([tuple([s,0]) for s in S[1]] + [tuple([t,1]) for t in T[0]]) == set(([phi(tuple([s,0])) for s in S[0]] + [phi(tuple([t,1])) for t in T[1]]))
def sijectionQ4(S, phi, T):
    return set([tuple([s,0]) for s in S[0]] + [tuple([t,1]) for t in T[1]]) == set(([phi(tuple([s,0])) for s in S[1]] + [phi(tuple([t,1])) for t in T[0]]))
def sijectionQ(S, phi, T):
    return sijectionQ1(S, phi, T) and sijectionQ2(S, phi, T) and sijectionQ3(S, phi, T) and sijectionQ4(S, phi, T)

## sijectiontoempty is the natural sijection S \sqcup -S => 0.
def sijectiontoempty(x):
    return ((x[0][0], 1 - x[0][1]), x[1])

## sijectionidentity is the natural sijection S => S.
def sijectionidentity(x):
    return (x[0], 1 - x[1])

## sijectioninverse(phi) is the inverse of the sijection phi.
def sijectioninverse(phi):
    def psi(x):
        y = phi((x[0], 1 - x[1]))
        return (y[0], 1 - y[1])
    return psi

## sijectioncommute is the natural sijection S \sqcup T => T \sqcup S.
def sijectioncommute(x):
    return ((x[0][0], 1 - x[0][1]), 1 - x[1])

## sijectioncartesiancommute(i) is the natural sijection
## S_0 x ... x S_i x S_(i+1) x S_(i+2) ... => S_0 x ... x S_(i+1) x S_i x S_(i+2) ...
def sijectioncartesiancommute(i):
    return (lambda x: (tuple(list(x[0][:i]) + [x[0][i + 1], x[0][i]] + list(x[0][i + 2:])), 1 - x[1]))

## sijectionaddzero is the natural sijection S => S \sqcup 0.
def sijectionaddzero(x):
    if x[1] == 0:
        return (x, 1)
    else:
        return x[0]

## sijectioncompose(pphi) computes the composition of sijections in the list pphi using the 
## Garsia--Milne involution principle (it goes through the list from left to right).
def sijectioncompose(pphi):
    if pphi == []:
        return sijectionidentity
    else:
        phi = sijectioncompose(pphi[:-1])
        psi = pphi[-1]
        def tau(x):
            if x[1] == 0:
                s = phi(x)
                i = 0
                while s[1] == 1:
                    if i == 0:
                        s = psi(tuple([s[0],0]))
                        s = tuple([s[0],s[1]+1])
                    else:
                        s = phi(s)
                    i = 1 - i
                if s[1] == 0:
                    return s
                else:
                    return tuple([s[0],1])
            else:
                s = psi(x)
                i = 0
                s = tuple([s[0],s[1]+1])
                while s[1] == 1:
                    if i == 0:
                        s = phi(s)
                    else:
                        s = psi(tuple([s[0],0]))
                        s = tuple([s[0],s[1]+1])
                    i = 1 - i
                if s[1] == 0:
                    return s
                else:
                    return tuple([s[0],1])
        return tau

## sijectioncartesian(pphi) computes the Cartesian product of a list pphi of sijections.
def sijectioncartesian(pphi):
    def psi(x):
        res = tuple([pphi[i](tuple([x[0][i],x[1]])) for i in range(len(x[0]))])
        if all([u[1] == 1 - x[1] for u in res]):
            return tuple([tuple([u[0] for u in res]),1-x[1]])
        else:
            j = 0
            while res[j][1] == 1 - x[1]:
                j += 1
            return tuple([tuple(list(x[0][:j]) + [res[j][0]] + list(x[0][j+1:])),x[1]])
    return psi

## sijectiondoubledisjointunion is the natural sijection that maps a disjoint union over
## S1 x S2 x ... to a double disjoint union, the outer one over S1, and the inner one over S2 x ...
def sijectiondoubledisjointunion(x):
    if x[1] == 0:
        return (((x[0][0], x[0][1][1:]), x[0][1][0]), 1)
    else:
        return ((x[0][0][0], tuple([x[0][1]] + list(x[0][0][1]))), 0)

## sijectioninnerdisjointunion is the natural sijection that maps a disjoint union,
## where the indexing set is a disjoint union, to a double disjoint union.
def sijectioninnerdisjointunion(x):
    if x[1] == 0:
        return (((x[0][0], x[0][1][0]), x[0][1][1]), 1)
    else:
        return ((x[0][0][0], (x[0][0][1], x[0][1])), 0)

## sijectiondistributivity(i) is the natural sijection that maps a cartesian product with a disjoint
## union of two signed sets in the i-th position to a disjoint unionof two cartesian products:
## S_0 x ... x (S_i' \sqcup S_i'') x ... => S_0 x ... X S_i' x ... \sqcup S_0 x ... X S_i'' x ...
def sijectiondistributivity(i):
    def tau(x):
        #print("x,i = ",x," ",i)
        if x[1] == 0:
            return ((tuple(list(x[0][:i]) + [x[0][i][0]] + list(x[0][i+1:])),x[0][i][1]),1)
        else:
            return (tuple(list(x[0][0][:i]) + [(x[0][0][i],x[0][1])] + list(x[0][0][i+1:])),0)
    return tau

## sijectiondistributivity1 is the natural sijection A x \sqcup S_t => \sqcup (A x S_t).
def sijectiondistributivity1(x):
    if x[1] == 0:
        return (((x[0][0], x[0][1][0]), x[0][1][1]), 1)
    else:
        return ((x[0][0][0], (x[0][0][1], x[0][1])), 0)
    #return (lambda x: (tuple([tuple([tuple([x[0][0],x[0][1][0]]),x[0][1][1]]),1])) if x[1] == 0 else (tuple([tuple([x[0][0][0],tuple([x[0][0][1],x[0][1]])]),0])))

## sijectiondistributivity1b is sijectiondistributivity(i) with i being the last position.
def sijectiondistributivity1b(x):
    if x[1] == 0:
        return ((tuple(list(x[0][:-1]) + [x[0][-1][0]]), x[0][-1][1]), 1)
    else:
        return (tuple(list(x[0][0][:-1]) + [(x[0][0][-1], x[0][1])]), 0)
    #return (lambda x: (tuple([tuple([tuple(list(x[0][:-1]) + [x[0][-1][0]]),x[0][-1][1]]),1])) if x[1] == 0 else (tuple([tuple(list(x[0][0][:-1]) + [tuple([x[0][0][-1],x[0][1]])]),0])))

## sijectiondistributivity2 is the natural sijection (\sqcup S_t) x A => \sqcup (S_t x A).
def sijectiondistributivity2(x):
    if x[1] == 0:
        return (((x[0][0][0], x[0][1]), x[0][0][1]), 1)
    else:
        return (((x[0][0][0], x[0][1]), x[0][0][1]), 0)
    #return (lambda x: (tuple([tuple([tuple([x[0][0][0],x[0][1]]),x[0][0][1]]),1])) if x[1] == 0 else (tuple([tuple([tuple([x[0][0][0],x[0][1]]),x[0][0][1]]),0])))

## sijectionplusminus takes a BIJECTION psi (with inverse psiinv) between the sets
## S0 \cup S1 and T0 \cup T1 and gives a sijection between two disjoint unions, where the
## one on the left is indexed by S, and the one on the right by T.
def sijectionplusminus(psi, psiinv):
    return (lambda x: tuple([tuple([x[0][0],(psi(x[0][1])) if x[1] == 0 else (psiinv(x[0][1]))]),1-x[1]]))

## sijectiontolists gives a sijection S => (S), where the elements of (S) are (s) for s in S.
def sijectiontolists(x):
    if x[1] == 0:
        return ((x[0],), 1)
    else:
        return (x[0][0],0)
    #return (lambda x: (tuple([tuple([x[0]]),1])) if x[1] == 0 else (tuple([x[0][0],0])))

## sijectionswitchouterdisjointunions gives the sijection \sqcup \sqcup A => \sqcup \sqcup A, 
## where the outer (resp. inner) disjoint union on the left is over T (resp. S) and
## the outer (resp. inner) disjoint union on the right is over S (resp. T).
def sijectionswitchouterdisjointunions(x):
    return (((x[0][0][0], x[0][1]), x[0][0][1]), 1 - x[1])
    #return (lambda x: (tuple([tuple([tuple([x[0][0][0],x[0][1]]),x[0][0][1]]),1-x[1]])))

## sijectionprepend is the natural sijection T x (S1 x S2 x ...) => T x S1 x S2 x ...
def sijectionprepend(x):
    if x[1] == 0:
        return (tuple([x[0][0]] + list(x[0][1])), 1)
    else:
        return ((x[0][0], x[0][1:]), 0)
    #return (lambda x: (tuple([tuple([x[0][0]] + list(x[0][1])),1])) if x[1] == 0 else (tuple([tuple([x[0][0],x[0][1:]]),0])))

## sijectionappend is the natural sijection (S1 x S2 x ...) x T => S1 x S2 x ... x T.
def sijectionappend(x):
    #return (lambda x: (tuple([tuple(list(x[0][0]) + [x[0][1]]),1])) if x[1] == 0 else (tuple([tuple([x[0][:-1],x[0][-1]]),0])))
    if x[1] == 0:
        return (x[0][0] + (x[0][1],), 1)
    else:
        return ((x[0][:-1], x[0][-1]), 0)

## sijectiondisjointunionassociativity1 is the natural sijection
## S0 \sqcup S1 \sqcup ... \squp S_(n-2) \sqcup (S_(n-1)' \sqcup S_(n-1)'') =>
## S0 \sqcup S1 \sqcup ... \sqcup S_(n-2) \sqcup S_(n-1)' \sqcup S_(n-1)''
def sijectiondisjointunionassociativity1(n):
    return (lambda x: ((tuple([x[0],1])) if x[0][1] <= n-2 else (tuple([tuple([x[0][0][0],n-1+x[0][0][1]]),1]))) if x[1] == 0 else ((tuple([x[0],0])) if x[0][1] <= n-2 else (tuple([tuple([tuple([x[0][0],x[0][1]-n+1]),n-1]),0]))))

#def sijectiondisjointunionassociativity(i):
#    return (lambda x: ((tuple([x[0],0])) if x[0][1] < i else ((tuple([tuple([x[0][0][0],i+x[0][0][1]]),1])) if x[0][1] == i else (tuple([tuple([x[0][0],x[0][1]+1]),1])))) if x[1] == 0 else ((tuple([x[0],0])) if x[0][1] < i else ((tuple([tuple([tuple([x[0][0],x[0][1]-i]),i]),0])) if i <= x[0][1] <= i+1 else (tuple([tuple([x[0][0],x[0][1]-1]),0])))))

## sijectiondisjointunionassociativity is the natural sijection
## S0 \sqcup S1 \sqcup ... \squp S_(i-1) \sqcup (S_(i)' \sqcup S_(i)'') \sqcup S_(i+1) ... =>
## S0 \sqcup S1 \sqcup ... \squp S_(i-1) \sqcup S_(i)' \sqcup S_(i)'' \sqcup S_(i+1) ... =>
def sijectiondisjointunionassociativity(i):
    def tau(x):
        if x[1] == 0:
            if x[0][1] < i:
                return (x[0],1)
            elif x[0][1] == i:
                return ((x[0][0][0],i+x[0][0][1]),1)
            else:
                return ((x[0][0],x[0][1]+1),1)
        else:
            if x[0][1] < i:
                return (x[0],0)
            elif i <= x[0][1] <= i + 1:
                return (((x[0][0],x[0][1]-i),i),0)
            else:
                return ((x[0][0],x[0][1]-1),0)
    return tau

## sijectiondisjointunion(psi, phit) gives the sijection \sqcup S_t => \sqcup S_t, where the
## disjoint union on the left (resp. right) is indexed by T (resp. T'), psi : T = > T' is a
## sijection, and phit(t) is a sijection S_t => S_(psi(t)).
def sijectiondisjointunion(psi, phit):
    def tau(x):
        ((s,t),i) = x
        (tp,j) = psi((t,i))
        (sp,jp) = phit((t,i))((s,0))
        return ((sp,t if jp == 0 else tp),1-i if jp == 1 and j != i else i)
    return tau

## sijdisun(phi) is a special case of sijectiondisjointunion where psi : T = > T is the identity.
def sijdisun(phi):
    return sijectiondisjointunion(sijectionidentity,lambda x: (lambda t: phi(x[0])(t)) if x[1] == 0 else (sijectioninverse(lambda t: phi(x[0])(t))))

## sijectiondisjointunion2(phi1, phi2) is the sijection S1 \sqcup S2 => T1 \sqcup T2 for
## sijections phi1: S1 => T1 and phi2: S2 => T2.
def sijectiondisjointunion2(phi1,phi2):
    def tau(x):
        return sijdisun(lambda i: (lambda t: phi1(t)) if i == 0 else (lambda t: phi2(t)))(x) 
    return tau

## -------------------------------------------------------------
## These are specialized sijections constructed in Problems 1--10 of Part I.
## -------------------------------------------------------------

## alpha is the sijection from Problem 1
def alpha(a,b,c):
    return (lambda x: (tuple([tuple([x[0],0]),1]) if (x[0] in sselements(ssinterval(a,b)))
            else tuple([tuple([x[0],1]),1])) if x[1] == 0 else (tuple([x[0][0],0]) if
            (x[0][0] in sselements(ssinterval(a,c))) else
            tuple([tuple([x[0][0],1-x[0][1]]),1])))

## beta is the sijection from Problem 2
def beta(aa,bb,x):
    if len(aa) == len(bb) == 0:
        return (lambda x: x)
    elif len(aa) == len(bb) == 1:
        return sijectioncompose([sijectioninverse(sijectiontolists),alpha(aa[0],x,bb[0]),sijectiondisjointunion2(sijectiontolists,sijectiontolists),sijectionplusminus(lambda i: tuple([(aa[0],0)]) if i == 0 else tuple([(bb[0]+1,1)]),lambda u: 0 if u == tuple([(aa[0],0)]) else 1)])
    else:
        return sijectioncompose([sijectioninverse(sijectionprepend),
                                 sijectioncartesian([sijectionidentity, beta(aa[1:], bb[1:], x)]),
                                 sijectioncartesian([sijectionidentity, sijectiondoubledisjointunion]),
                                 sijectiondistributivity1,
                                 sijdisun(lambda i: sijectioncartesian([alpha(aa[0], i[0], bb[0]),sijectionidentity])),
                                 sijdisun(lambda q: sijectioncartesian([sijectionplusminus(lambda i: (aa[0],0) if i == 0 else (bb[0] + 1, 1),lambda u: 0 if u == (aa[0], 0) else 1), sijectionidentity])),
                                 sijdisun(lambda q: sijectiondistributivity2),
                                 sijdisun(lambda q: sijdisun(lambda r: sijectiondistributivity1)),
                                 sijdisun(lambda q: sijdisun(lambda r: sijdisun(lambda s: sijectionprepend))),
                                 sijectionswitchouterdisjointunions,
                                 sijdisun(lambda q: sijectioninverse(sijectiondoubledisjointunion)),
                                 sijectioninverse(sijectiondoubledisjointunion)])

## gamma is the sijection from Problem 3
def gamma(kk,x):
    def phi12(x,n):
        if x[1] == 0:
            if x[0][1] == 0 and x[0][0][1] == n:
                return (((x[0][0][0],n-2),0),1)
            elif x[0][1] == 0 and x[0][0][1] == n - 2:
                return (((x[0][0][0],n-1),0),1)
            elif x[0][1] == 0 and x[0][0][1] == n - 1:
                return (((x[0][0][0],n-3),1),1)
            else:
                return (x[0],1)
        else:
            if x[0][1] == 0 and x[0][0][1] == n-2:
                return (((x[0][0][0],n),0),0)
            elif x[0][1] == 0 and x[0][0][1] == n-1:
                return (((x[0][0][0],n-2),0),0)
            elif x[0][1] == 1 and x[0][0][1] == n-3:
                return (((x[0][0][0],n-1),0),0)
            else:
                return (x[0],0)
    if len(kk) == 1:
        return (lambda xx: xx)
    elif len(kk) == 2:
        def tau(xx):
            return (sijectioncompose([sijectioninverse(sijectiontolists),
                                 alpha(kk[0], x,  kk[1]),
                                 sijectioncommute,
                                 sijectiondisjointunion2(sijectiontolists, sijectiontolists),
                                 sijectionaddzero]))(xx)
        return tau
    else:
        return sijectioncompose([sijectioninverse(sijectionappend),
                                 sijectioncartesian([gamma(kk[:-1], x + 1), sijectionidentity]),
                                 sijectiondistributivity2,
                                 sijectiondisjointunion2(sijectiondistributivity2, sijectiondistributivity2),
                                 sijectiondisjointunion2(sijdisun(lambda i: sijectionappend), sijdisun(lambda j: sijectionappend)),
                                 sijectiondisjointunion2(sijdisun(lambda i: sijectioncartesian([sijectionidentity]*(len(kk)-2) + ([alpha(kk[-2], x, kk[-1])] if i == len(kk) - 2 else [sijectionidentity]))), sijectionidentity),
                                 sijectiondisjointunion2(sijdisun(lambda i: sijectiondistributivity1b if i == len(kk) - 2 else sijectionidentity), sijectionidentity) ,
                                 sijectiondisjointunion2(sijectiondisjointunionassociativity1(len(kk) - 1), sijectionidentity),
                                 sijectiondisjointunion2(sijdisun(lambda i: sijectioncartesian([sijectionidentity]*(len(kk)-3) + [alpha(kk[-3],kk[-2],x+1), sijectionidentity]) if i == len(kk) - 2 else sijectionidentity), sijectionidentity),
                                 sijdisun(lambda j: sijdisun(lambda i: sijectiondistributivity(len(kk) - 3) if i == len(kk) - 2 else sijectionidentity) if j == 0 else sijectionidentity),
                                 sijectiondisjointunion2(sijectiondisjointunionassociativity(len(kk)-2), sijectionidentity),
                                 lambda xx: phi12(xx,len(kk))])

## rho is the sijection from Problem 4
def rho(aa, bb, x):
    return sijectioncompose([sijectiondisjointunion(beta(aa,bb,x),
           lambda q: sijectionidentity),sijectioninnerdisjointunion])

## pi is the first sijection from Problem 5
def pi(kk,i):
    if len(kk) == 2 and i == 1:
        return sijectionidentity
    else:
        return sijectioncompose([
            sijectiondisjointunion(sijectioncompose([sijectioncartesian([sijectionidentity]*(i-2) +
            ([] if i == 1 else [alpha(kk[i-2],kk[i]+1,kk[i-1])]) + [sijectionidentity] +
            ([] if i == len(kk) - 1 else [sijectioncompose([alpha(kk[i],kk[i-1]-2,kk[i+1]),sijectioncommute])])
            + ([sijectionidentity]*(len(kk)-i-2) if len(kk)-i-2 >= 0 else [])),
            sijectionidentity if i == len(kk) - 1 else sijectiondistributivity(i),
            sijectionidentity if i == 1 else
            (sijectiondistributivity(i-2) if i == len(kk) - 1 else
            sijectiondisjointunion2(sijectiondistributivity(i-2),sijectiondistributivity(i-2))),
            sijectionidentity if i == 1 or i == len(kk) - 1 else
            (lambda x: ((x[0][0][0],x[0][1] + 2 * x[0][0][1]),1) if x[1] == 0 else
             (((x[0][0],x[0][1] // 2),x[0][1] % 2),0))]), lambda q: sijectionidentity),
            sijectioninnerdisjointunion,
            sijdisun(lambda j: sijectionidentity if j == 0 else
            sigma(tuple((list(kk[:i-2]) if i >= 3 else []) + ([kk[i-2],kk[i]+1,kk[i]] if 1 < i < len(kk) - 1 and j == 1
                else ([kk[i]+2,kk[i]+1,kk[i-1]-1] if 1 < i < len(kk) - 1 and j == 2 else
                ([kk[i]+2,kk[i]+1,kk[i]] if 1 < i < len(kk) - 1 and j == 3 else
                 ([kk[i]+1,kk[i]] if i == 1 and j == 1 else ([kk[i]+2,kk[i]+1]))))) +
                (list(kk[i+1:-1]) if i + 2 <= len(kk) - 1 else [])),
                  tuple((list(kk[1:i-1]) if 2 <= i - 1 else []) +
                ([kk[i]+1,kk[i-1]-1,kk[i-1]-2] if 1 < i < len(kk) - 1 and j == 1 else
                 ([kk[i-1],kk[i-1]-1,kk[i+1]] if 1 < i < len(kk) - 1 and j == 2 else
                  ([kk[i-1],kk[i-1],kk[i]-2] if 1 < i < len(kk) - 1 and j == 3 else
                   ([kk[i-1]-1,kk[i-1]-2] if i == 1 and j == 1 else
                    ([kk[i-1],kk[i-1]-1]))))) +
                (list(kk[i+2:]) if i+3 <= len(kk) else [])),
                  i if 1 < i < len(kk) - 1 and j == 1 else
                  (i-1 if 1 < i < len(kk) - 1 and j == 2 else
                   (i-1 if 1 < i < len(kk) - 1 and j == 3 else
                    (i if i == 1 and j == 1 else (i-1 if i == len(kk) - 1 and j == 1 else None)))))),
            lambda x: (x[0][0],1) if x[1] == 0 else ((x[0],0),0)])

## sigma is the second sijection from Problem 5
def sigma(aa,bb,i):
    def tau(x):
        ll = x[0][1]
        A = x[0][0]
        lp = tuple(list(ll[:i-1]) + [ll[i]+1,ll[i-1]-1] + list(ll[i+1:]))
        Ap = pi(ll,i)((A,0))
        if Ap[1] == 0:
            return ((Ap[0],ll),0)
        else:
            return ((Ap[0],lp),0)
    return tau

## tau is the sijection from Problem 6
def tau(kk,x):
    return sijectioncompose([sijectiondisjointunion(gamma(kk,x),lambda q: sijectionidentity),
                             sijectioninnerdisjointunion,
                             sijectiondisjointunion2(sijectioninnerdisjointunion,sijectioninnerdisjointunion),
                             sijectiondisjointunion2(sijectionidentity,
                                sijdisun(lambda i: sigma(tuple(list(kk[:i]) + [kk[i+1]+1,kk[i+1]] +
                                list(kk[i+2:-1])),tuple(list(kk[1:i+1]) + [x+len(kk)-i-2,x+len(kk)-i-3] +
                                list(kk[i+3:])),i+1))),
                             sijectioninverse(sijectionaddzero)])

## Xi is the sijection from Problem 7
def Xi(kk):
    n = len(kk)
    def tau(xx):
        if xx[1] == 0:
            return (((xx[0][:-1],xx[0][-2]),tuple([-1] +
            [(1) if xx[0][-1][i-1] <= xx[0][-1][i] == xx[0][-2][i-1] else
             (0 if xx[0][-1][i-1] > xx[0][-1][i] == xx[0][-2][i-1] ==
              xx[0][-2][i] > xx[0][-1][i+1] else -1) for i in range(1,n-1)] + [1])),1)
        else:
            mu = xx[0][1]
            if mu[0] != -1:
                return ((xx[0][0],tuple([1-mu[0]] + list(mu[1:]))),1)
            elif mu[-1] != 1:
                return ((xx[0][0],tuple(list(mu[:-1]) + [-1-mu[-1]])),1)
            else:
                i = 1
                end = False
                new = 0
                while (not(end) and i < n-1):
                    if kk[i-1] <= kk[i] == xx[0][0][0][-1][i-1]:
                        if mu[i] == 1:
                            i += 1
                        else:
                            new = -1 - mu[i]
                            end = True
                    elif kk[i-1] > kk[i] == xx[0][0][0][-1][i-1] == xx[0][0][0][-1][i] > kk[i+1]:
                        i += 1
                    elif kk[i-1] > kk[i] == xx[0][0][0][-1][i-1]:
                        if xx[0][0][0][-1][i-1] == xx[0][0][0][-1][i]:
                            i += 1
                        else:
                            new = -1 - mu[i]
                            end = True
                    else:
                        if mu[i] == -1:
                            i += 1
                        else:
                            new =  1 - mu[i]
                            end = True
                if i == n-1:
                    return (tuple(list(xx[0][0][0]) + [kk]),0)
                else:
                    return ((xx[0][0],tuple(list(mu[:i]) + [new] + list(mu[i+1:]))),1)
    return tau

## Psi is the sijection from Problem 8
def Psi(n,i):
    def tau(x):
        if x[1] == 0:
            f = APlisttoarray(x[0],n-1)
            T = AParraytolist(lambda a,b: f(a,b) if b < i else (f(a,b-1) if a < i < b else (f(a-1,b-1) if i < a else (1 if b == i else -1))),n)
            return (T,1)
        else:
            f = APlisttoarray(x[0], n)
            if all([f(j,i) == 1 for j in range(1,i)]) and all([f(i,j) == -1 for j in range(i+1,n+1)]):
                T = AParraytolist(lambda a,b: f(a,b) if b < i else (f(a,b+1) if a < i <= b else f(a+1,b+1)),n-1)
                return (T,0)
            elif all([f(j,i) == 1 for j in range(1,i)]):
                j = i + 1
                while j <= n and f(i,j) == -1:
                    j += 1
                T = AParraytolist(lambda a,b: 1 - f(a,b) if a == i and b == j else f(a,b),n)
                return (T,1)
            else:
                j = 1
                while j < i and f(j,i) == 1:
                    j += 1
                T = AParraytolist(lambda a,b: -1 - f(a,b) if a == j and b == i else f(a,b),n)
                return (T,1)
    return tau

## Phi1 is one of the auxilliary sijections from Problem 9
def Phi1(kk,x):
    n = len(kk)
    return sijectioncompose([sijdisun(lambda q: sijectionswitchouterdisjointunions),
                sijdisun(lambda q: sijdisun(lambda T: sijectiondisjointunion(
                    lambda xx: (tuple([xx[0][j] + (1 if xx[1] == 0 else -1)*c(T,n-1,j+1)
                    for j in range(n-1)]), 1-xx[1]), lambda r: sijectionidentity))),
                sijdisun(lambda mu: sijdisun(lambda T:
                    rho(tuple([kk[j] + (1 if mu[j] >= 0 else 0) + c(T,n-1,j+1) for j in range(n-1)]),
                        tuple([kk[j+1] - (1 if mu[j+1] <= 0 else 0) + c(T,n-1,j+1) for j in range(n-1)]),
                        x))),
                sijdisun(lambda q: sijdisun(lambda T: sijectiondisjointunion(
                    lambda xx: (tuple([(xx[0][j][0] - (1 if xx[1] == 0 else -1) * c(T,n-1,j+1),
                    xx[0][j][1]) for j in range(n-1)]), 1-xx[1]), lambda r: sijectionidentity)))])

## Phi2 is one of the auxilliary sijections from Problem 9
def Phi2(kk,x):
    n = len(kk)
    return sijdisun(lambda q: sijectiondisjointunion(Psi(n,n),lambda r: sijectionidentity))


## Phi3 is one of the auxilliary sijections from Problem 9
def Phi3(kk,x):
    def Phi3a(kk,x):
        n = len(kk)
        def tau(xx):
            if xx[1] == 0:
                i = 0
                while i < n-1 and xx[0][0][0][1][i][1] == 0:
                    i += 1
                j = i
                while i < n-1 and xx[0][0][0][1][i][1] == 1:
                    i += 1
                if i == n-1:
                    return ((((xx[0][0][0][0],j),xx[0][0][1]),xx[0][1]),1)
                else:
                    A = xx[0][0][0][0]
                    m = xx[0][0][0][1]
                    T = xx[0][0][1]
                    f = APlisttoarray(T, n)
                    mu = xx[0][1]
                    Ap = pi(tuple([m[j][0] + c(T,n,j+1) for j in range(n-1)] + [x]),i)((A,0))
                    if Ap[1] == 0:
                        return ((((Ap[0],m),T),mu),0)
                    else:
                        mup = tuple(list(mu[:i]) + [-f(i,i+1)] + list(mu[i+1:]))
                        Tp = AParraytolist(lambda a,b: (-mu[i]) if a==i and b==i+1 else
                            (f(i+1,b) if a == i else (f(i,b) if a == i+1 else
                            (f(a,i) if b == i+1 else (f(a,i+1) if b == i else f(a,b))))),n)
                        mp = tuple([(m[j][0],m[j][1]) for j in range(i-1)]
                            + [(kk[i] - (1 if mup[i] <= 0 else 0)+1,m[i-1][1]),
                               (kk[i] + (1 if mup[i] >= 0 else 0),m[i][1])]
                            + [(m[j][0],m[j][1]) for j in range(i+1,len(m))])
                        return ((((Ap[0],mp),Tp),mup),0)
            else:
                return ((((xx[0][0][0][0],tuple(
                    [(kk[j] + (1 if xx[0][1][j] >= 0 else 0),0) for j in range(xx[0][0][0][1])]
                    +[(kk[j] - (1 if xx[0][1][j] <= 0 else 0) + 1,1) for j in range(xx[0][0][0][1]+1,n)]
                    )),xx[0][0][1]),xx[0][1]),0)
        return tau
    def Phi3b(kk,x):
        n = len(kk)
        def tau():
            def aaa(mu,T,i):
                return sijectioncompose([pi(
            tuple([kk[l] + (1 if mu[l] >= 0 else 0) + c(T,n,l+1) for l in range(i)]
                + [kk[l] - (1 if mu[l] <= 0 else 0) + c(T,n,l) + 1 for l in range(i+1,j)]
                + [x+n-j]
                + [kk[l] - (1 if mu[l] <= 0 else 0) + c(T,n,l) for l in range(j,n)]),
                                 j-1) for j in range(n,i+1,-1)])
            return sijdisun(lambda mu: sijdisun(lambda T: sijdisun(lambda i: sijectioncompose([pi(
            tuple([kk[l] + (1 if mu[l] >= 0 else 0) + c(T,n,l+1) for l in range(i)]
                + [kk[l] - (1 if mu[l] <= 0 else 0) + c(T,n,l) + 1 for l in range(i+1,j)]
                + [x+n-j]
                + [kk[l] - (1 if mu[l] <= 0 else 0) + c(T,n,l) for l in range(j,n)]),
                                 j-1) for j in range(n,i+1,-1)]))))
        return tau()
    return sijectioncompose([Phi3a(kk,x),Phi3b(kk,x)])

## Phi4 is one of the auxilliary sijections from Problem 9
def Phi4(kk,x):
    def Lambda(n,i):
        def tau(x):
            if x[1] == 0:
                if x[0] == tuple([-1]*i + [1]*(n-i)):
                    return (0,1)
                else:
                    j = 0
                    while j < i and x[0][j] == -1 or j >= i and x[0][j] == 1:
                        j += 1
                    return (tuple(list(x[0][:j]) + [1 - x[0][j] if j < i else -1 - x[0][j]] + list(x[0][j+1:])),0)
            else:
                return (tuple([-1]*i + [1]*(n-i)),0)
        return tau
    n = len(kk)
    return sijectioncompose([sijectionswitchouterdisjointunions,
        sijdisun(lambda q: sijectionswitchouterdisjointunions),
        sijdisun(lambda q: sijdisun(lambda i:
                sijectiondisjointunion(Lambda(n,i+1),lambda r: sijectionidentity))),
        sijdisun(lambda q: sijdisun(lambda i:
                                    (lambda xx: (xx[0][0],1) if xx[1]==0 else ((xx[0],0),0)))),
        sijectionswitchouterdisjointunions,
        sijdisun(lambda i: sijectiondisjointunion(
            sijectioncompose([sijectioninverse(Psi(n,n)),Psi(n,i+1)]),lambda r: sijectionidentity)),
        sijectionswitchouterdisjointunions,
        sijdisun(lambda T:
            sijectioninverse(tau(tuple([kk[i] + c(T,n,i+1) for i in range(n)]),x)))
        ])

## Phi is the sijection from Problem 9
def Phi(kk,x):
    return sijectioncompose([Phi1(kk,x),Phi2(kk,x),Phi3(kk,x),Phi4(kk,x)])

## Gamma is the sijection from Problem 10
def Gamma(kk,x):
    def tau(xx):
        if len(kk) == 1:
            if xx[1] == 0:
                return ((tuple([]),tuple([])),1)
            else:
                return (((kk[0],),),0)
        else:
            return sijectioncompose([Xi(kk), sijdisun(lambda q: sijdisun(lambda r:
                Gamma(r,x))), Phi(kk,x)])(xx)
    return tau

## -------------------------------------------------------------
## With the code below, we check that the definitions above indeed give
## required sijections (via examples). Uncommented and change input at will.
## -------------------------------------------------------------

## -------------------------------------------------------------
## checking beta
##
##aa = (1, 4, 2, -3, 5)
##bb = (4, 8, 2, 0, 2)
##x = 5
##
##start = time.time()
##S = sscartesian([ssinterval(aa[i],bb[i]) for i in range(len(aa))])
##T = ssdisjointunion(sscartesian([ssdisjointunion2(([aa[i]],[]),([],[bb[i]+1])) for i in range(len(aa))]),lambda l: sscartesian([ssinterval(l[i][0],l[i+1][0] if i < len(l) - 1 else x) for i in range(len(l))]))
##phi = beta(aa,bb,x)
##print("S: ",len(S[0])," ",len(S[1]))
##print("T: ",len(T[0])," ",len(T[1]))
##print(time.time() - start)
##
##start = time.time()
##print(sijectionQ(S,beta(aa,bb,x),T))
##print(time.time() - start)
## -------------------------------------------------------------

## -------------------------------------------------------------
##checking gamma
##
##kk = (1, 3, 4, 6, 8, 9, 13, 15)
##x = 3

##start = time.time()
##S = sscartesian([ssinterval(kk[i],kk[i+1]) for i in range(len(kk) - 1)])
##T = ssdisjointunion2(ssdisjointunion(ssinterval(0,len(kk)-1),lambda i:
##                    sscartesian([ssinterval(kk[j],kk[j+1]) for j in range(i-1)] +
##                    ([ssinterval(kk[i-1],x+len(kk)-i-1)] if i > 0 else []) +
##                    ([ssinterval(x+len(kk)-i-1,kk[i+1])] if i < len(kk) - 1 else []) +
##                    [ssinterval(kk[j],kk[j+1]) for j in range(i+1,len(kk)-1)])),
##                    ssdisjointunion(ssinterval(0,len(kk)-3),lambda i:
##                    sscartesian([ssinterval(kk[j],kk[j+1]) for j in range(i)] +
##                    [ssinterval(kk[i+1]+1,x+len(kk)-i-2), ssinterval(kk[i+1],x+len(kk)-i-3)] +
##                    [ssinterval(kk[j],kk[j+1]) for j in range(i+2,len(kk)-1)])))
##print("S: ",len(S[0])," ",len(S[1]))
##print("T: ",len(T[0])," ",len(T[1]))
##print(time.time() - start)
##
##start = time.time()
##print(sijectionQ(S,gamma(kk,x),T))
##print(time.time() - start)
## -------------------------------------------------------------

## -------------------------------------------------------------
## checking rho
##
##aa = (1, 4, -2)
##bb = (4, 8, 4)
##x = 3
##
##start = time.time()
##S = ssdisjointunion(sscartesian([ssinterval(aa[i],bb[i]) for i in range(len(aa))]),lambda l: GT(l))
##T = ssdisjointunion(sscartesian([ssdisjointunion2(([aa[i]],[]),([],[bb[i]+1])) for i in range(len(aa))]),lambda l: GT([i[0] for i in l] + [x]))
##print("S: ",len(S[0])," ",len(S[1]))
##print("T: ",len(T[0])," ",len(T[1]))
##print(time.time() - start)
##
##start = time.time()
##print(sijectionQ(S,rho(aa,bb,x),T))
##print(time.time() - start)         
## -------------------------------------------------------------

## -------------------------------------------------------------
## checking pi
##kk = (1, 3, 6, 2)
##i = 2
##
##start = time.time()
##S = GT(kk)
##T = GT(tuple(list(kk[:i-1]) + [kk[i]+1,kk[i-1]-1] + list(kk[i+1:])))
##print("S: ",len(S[0])," ",len(S[1]))
##print("T: ",len(T[0])," ",len(T[1]))
##print(time.time() - start)
##
##start = time.time()
##print(sijectionQ(S,pi(kk,i),ssminus(T)))
##print(time.time() - start)
## -------------------------------------------------------------

## -------------------------------------------------------------
## checking sigma
##aa = (4, 1, 0, 3)
##bb = (1, 4, 3, 5)
##i = 2
##
##start = time.time()
##S = ssdisjointunion(sscartesian([ssinterval(aa[i],bb[i]) for i in range(len(aa))]),lambda q: GT(q))
##print("S: ",len(S[0])," ",len(S[1]))
##print(time.time() - start)
##
##start = time.time()
##print(sijectionQ(S,sigma(aa,bb,i),ssempty()))
##print(time.time() - start)
## -------------------------------------------------------------

## -------------------------------------------------------------
## checking tau
##
##kk = (1, 5, 2, -4)
##x = 6
##
##start = time.time()
##S = GT(kk)
##T = ssdisjointunion(ssinterval(0,len(kk)-1), lambda i:
##                    GT(tuple(list(kk[:i]) + [x+len(kk)-i-1] + list(kk[i+1:]))))
##print("S: ",len(S[0])," ",len(S[1]))
##print("T: ",len(T[0])," ",len(T[1]))
##print(time.time() - start)
##
##start = time.time()
##print(sijectionQ(S,tau(kk,x),T))
##print(time.time() - start)
## -------------------------------------------------------------

## -------------------------------------------------------------
## checking Xi
##
##kk = (1, 3, -2, 5)
##
##start = time.time()
##S = MT(kk)
##T = ssdisjointunion(AR(len(kk)),lambda mu: ssdisjointunion(
##    sscartesian([ssinterval(kk[i] + (1 if mu[i] >= 0 else 0),
##                            kk[i+1] - (1 if mu[i+1] <= 0 else 0)) for i in range(len(kk)-1)]),
##        lambda l: MT(l)))
##print("S: ",len(S[0])," ",len(S[1]))
##print("T: ",len(T[0])," ",len(T[1]))
##print(time.time() - start)
##
##start = time.time()
##print(sijectionQ(S,Xi(kk),T))
##print(time.time() - start)
## -------------------------------------------------------------

## -------------------------------------------------------------
## checking Psi
##
## n = 4
##
##start = time.time()
##S = AP(n-1)
##T = AP(n)
##print(time.time() - start)
##
##start = time.time()
##print([sijectionQ(S,Psi(n,i),T) for i in range(1,n+1)])
##print(time.time() - start)
## -------------------------------------------------------------

## -------------------------------------------------------------
## checking Phi
##kk = (1,2,3)
##x = 4
##
##start = time.time()
##S = ssdisjointunion(AR(n),lambda mu: ssdisjointunion(
##    sscartesian([ssinterval(kk[i] + (1 if mu[i] >= 0 else 0),
##                            kk[i+1] - (1 if mu[i+1] <= 0 else 0)) for i in range(len(kk)-1)]),
##    lambda l: SGT(l)))
##T = SGT(kk)
##print("S: ",len(S[0])," ",len(S[1]))
##print("T: ",len(T[0])," ",len(T[1]))
##print(time.time() - start)
##
##start = time.time()
##print("Phi: ", sijectionQ(S,Phi(kk,x),T))
##print(time.time() - start)


## -------------------------------------------------------------
## checking Gamma
##kk = (1,2,3)
##x = 0
##
##start = time.time()
##S = MT(kk)
##print("S: ",len(S[0])," ",len(S[1]))
##T = SGT(kk)
##print("T: ",len(T[0])," ",len(T[1]))
##print(time.time() - start)
##
##start = time.time()
##print(sijectionQ(S,Gamma(kk,x),T))
##print(time.time() - start)
## -------------------------------------------------------------

##print("T: ",len(T[0])," ",len(T[1]))
##phi = detcommute(m)
##print(sijectionQ(S, phi, T))
##print(time.time() - start)