## 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

from ASMcodePartI import *

import random

## -------------------------------------------------------------
## The following are some sets and signed sets that we need. Most are defined in Part II.
## -------------------------------------------------------------

## cartesian(A) computes the cartesian product of a list A of sets.
def cartesian(A):
    return list(itertools.product(*A))

## A(n) constructs all alternating sign matrices of size n x n.
def A(n):
    return [MTtoASM((T, 0))[0] for T in montriang(tuple(range(1, n + 1)))]

## Ai(n, i) constructs all alternating sign matrices of size n x n with 1 in row 1 and column i.
def Ai(n, i):
    if i in range(1, n + 1):
        return list(filter(lambda T:T[0][i - 1] == 1, A(n)))
    else:
        return []

## subsets(S) constructs all subsets of the set S.
def subsets(S):
    return list(itertools.chain.from_iterable(itertools.combinations(list(S), r) for r in range(len(S)+1)))

## subsets(S) constructs all k-element subsets of the set S.
def ksubsets(n, k):
    if k < 0:
        return []
    else:
        return list(itertools.combinations(range(1,n+1), k))

## compositions(n, k) constructs all compositions of integer n with k parts.
def compositions(n, k):
    if n < 0 or k < 0:
        return []
    elif k == 0:
        if n == 0:
            return [tuple([])]
    elif k == 1:
        return [(n,)]
    else:
        u = []
        for i in range(0,n+1):
            for comp in compositions(n-i,k-1):
                u += [tuple(list(comp) + [i])]
        return u

## B(n) constructs all (2 n - 1)-element subsets of [3 n - 2].
def B(n):
    return ksubsets(3*n-2,2*n-1)

## B(n, i) constructs all (2 n - 1)-element subsets of [3 n - 2] whose median is n + i - 1.
def Bi(n, i):
    return list(filter(lambda S:S[n - 1]==n + i - 1,B(n)))

## perm_parity(pi) returns 1 if pi is an even permutation and -1 otherwise.
def perm_parity(pi):
    c = 0
    n = len(pi)
    for i in range(n):
        for j in range(i+1,n):
            if pi[i] > pi[j]:
                c += 1
    return 1 if c % 2 == 0 else -1  

## perms(n) constructs all permutations of n elements.
def perms(n):
    S = list(itertools.permutations(range(1,n+1)))
    return (list(filter(lambda pi: perm_parity(pi) == 1,S)), list(filter(lambda pi: perm_parity(pi) == -1,S)))

## det(P) constructs the "determinant" of P, i.e. the disjoint union of P_(1,pi(1)) x ...
## x P_(m,pi(m)) over all permutations pi in S_m.
def det(P):
    m = len(P)
    return ssdisjointunion(perms(m), lambda pi: sscartesian([P[i][pi[i]-1] for i in range(m)]))

## Ej(kk, j) constructs the set E_j defined in the beginning of Section 3 in Part II.
def Ej(kk, j):
    n = len(kk)
    return ssdisjointunion((ksubsets(n, j),[]), lambda V: ssdisjointunion((subsets(V),[]),
            lambda U: sspm(len(U))(GT(tuple([kk[i] + (1 if i+1 in U else 0)
                        for i in range(n)])))))

## Fj(kk, j) constructs the set F_j defined in the beginning of Section 3 in Part II.
def Fj(kk, j):
    n = len(kk)
    return ssdisjointunion((ksubsets(n, j),[]), lambda V: ssdisjointunion((subsets(V),[]),
            lambda U: sspm(len(U))(GT(tuple([kk[i] - (1 if i+1 in U else 0)
                        for i in range(n)])))))

## Ejprime(kk, j) constructs the set E'_j defined in the middle of Section 3 in Part II.
def Ejprime(kk, j):
    n = len(kk)
    return ssdisjointunion((list(map(lambda S: tuple(S[i]+1 for i in range(len(S))),ksubsets(n-1,j))),[]),
                           lambda V: ssdisjointunion((subsets(V),[]),
            lambda U: sspm(len(U))(GT(tuple([kk[i] + (1 if i+1 in U else 0)
                        for i in range(n)])))))

## Fjprime(kk, j) constructs the set F'_j defined in the middle of Section 3 in Part II.
def Fjprime(kk, j):
    n = len(kk)
    return ssdisjointunion((list(map(lambda S: tuple(S[i]+1 for i in range(len(S))),ksubsets(n-1,j))),[]),
                           lambda V: ssdisjointunion((subsets(V),[]),
            lambda U: sspm(len(U))(GT(tuple([kk[i] - (1 if i+1 in U else 0)
                        for i in range(n)])))))

## MTtoASM is the natural bijection between monotone triangles with bottom row (1, 2, ..., n)
## and alternating sign matrices of size n x n.
def MTtoASM(x):
    T = x[0]
    n = len(T)
    if x[1] == 0:
        return (tuple([tuple([1 if (j+1 in T[i] and (i == 0 or j+1 not in T[i-1]))
            else (-1 if j+1 not in T[i] and i > 0 and j+1 in T[i-1] else 0)
                for j in range(n)]) for i in range(n)]),1)
    else:
        return (tuple([tuple([q+1 for q, r in enumerate([sum([T[p][j] for p in range(i+1)])
                for j in range(n)]) if r == 1]) for i in range(n)]),0)

## addleft(Tp, mu, n) adds the arrow row mu as the left-most diagonal to an arrow pattern Tp.
def addleft(Tp, mu, n):
    f = APlisttoarray(Tp,n-1)
    return AParraytolist(lambda i,j: mu[j-2] if i == 1 else f(i-1,j-1), n)

## addright(Tp, mu, n) adds the arrow row mu as the right-most diagonal to an arrow pattern Tp. 
def addright(Tp,mu,n):
    f = APlisttoarray(Tp,n-1)
    return AParraytolist(lambda i,j: mu[i-1] if j == n else f(i,j), n)

## rot(kk) transforms (kk_1, ... k_n) to (kk_2, ..., kk_n, kk_1 - n)
def rot(kk):
    return tuple(list(kk[1:]) + [kk[0]-len(kk)])

## MTsubit(kk, i) gives MT_i from Section 4 of Part II.
def MTsubi(kk, i):
    if i > len(kk):
        return ssempty()
    else:
        return (list(filter(lambda A: (i == len(kk) or A[-i-1][0] != kk[0])
            and all([A[-j-1][0] == kk[0] for j in range(i)]), MT(kk)[0])),[])

## MTsupit(kk, i) gives MT^i from Section 4 of Part II.
def MTsupi(kk,i):
    if i > len(kk):
        return ssempty()
    else:
        return (list(filter(lambda A: (i == len(kk) or A[-i-1][-1] != kk[-1])
            and all([A[-j-1][-1] == kk[-1] for j in range(i)]), MT(kk)[0])),[])

## DPP(n) gives all descending plane partitions with parts <= n.
def DPP(n):
    def rows(n, k):
        if k == 0:
            return [[]]
        else:
            return [[i] + u for i in range(n, -1, -1) for u in rows(i, k - 1)]
    if n < 2:
        return [()]
    if n == 2:
        return [(), ((2,),)]
    first_row = [[n] + u for u in rows(n, n - 2)]
    q = DPP(n-1)
    for row in first_row:
        w = tuple(filter(lambda r: r > 0, row))
        q += [tuple([w] + list(u)) for u in list(filter(lambda T: T == () or T[0][0] <= len(w) and all([T[0][i] < row[i + 1] for i in range(len(T[0]))]), DPP(row[1] - 1)))]
    return q

## DPP(n, i) gives all descending plane partitions with parts <= n and exactly i - 1 n's.
def DPPi(n, i):
    return list(filter(lambda A: len(A) == 0 and i == 1 or len(A) > 0 and A[0].count(n) == i-1, DPP(n)))

## matrixsum(A, B, i, j) gives the sum of i x j matrices A and B.
def matrixsum(A, B, i, j):
    return [[ssdisjointunion2(A[p][q], B[p][q]) for q in range(j)] for p in range(i)]

## matrixproduct(A, B, i, k, j) gives the product of an i x k matrix B and a k x j matrix B.
def matrixproduct(A, B, i, k, j):
    return [[ssdisjointunion(ssinterval(1,k), lambda r: sscartesian([A[p][r-1], B[r-1][q]]))
             for q in range(j)] for p in range(i)]

## Given a sijection phi: S \sqcup T => ssempty(), fromsijectiontoempty constructs a
## sijection S => -T.
def fromsijectiontoempty(phi):
    return lambda x: phi((x, 0))[0]

## Given a signed set S of size 0, sijectiontoempty(S) gives a sijection S => ssempty().
## Use only in examples. Do not use in sijection constructions.
def sijectiontoempty(S):
    def tau(x):
        if x[0] in S[0]:
            return (S[1][S[0].index(x[0])], 0)
        else:
            return (S[0][S[1].index(x[0])], 0)
    if sssize(S) == 0:
        return tau
    else:
        return None

## bijectionQ(S, phi, T) checks that phi is a bijection 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.
## bijectionQfast is faster.
def bijectionQ1(S, phi, T):
    return all([phi(phi((s,0))) == (s,0) for s in S])
def bijectionQ2(S, phi, T):
    return all([phi(phi((t,1))) == (t,1) for t in T])
def bijectionQ3(S, phi, T):
    return set([(s,0) for s in S]) == set([phi((t,1)) for t in T])
def bijectionQ4(S, phi, T):
    return set([(t,1) for t in T]) == set([phi((s,0)) for s in S])
def bijectionQ(S, phi, T):
    return bijectionQ1(S, phi, T) and bijectionQ2(S, phi, T) and bijectionQ3(S, phi, T) and bijectionQ4(S, phi, T)
def bijectionQfast(S, phi, T):
    U = [phi((s,0))[0] for s in S]
    V = [phi((t,1))[0] for t in U]
    return len(S) == len(T) and V == S and set(U) == set(T)

## complement(n) is the bijection that maps a subset of {1, ..., n} to its complement. 
def complement(n):
    return (lambda x: (tuple(sorted(list(set(range(1,n+1)) - set(x[0])))), 1 - x[1]))

## perminverse maps a permutation to its inverse.
def perminverse(x):
    pi = x[0]
    inverse = [0] * len(pi)
    for i, p in enumerate(pi):
        inverse[p-1] = i+1
    return (tuple(inverse),1-x[1])

## subsetstocompositions(n, k) is the natural bijection between k-subsets of {1, ..., n}
## and compositions of n - k with k + 1 parts.
def subsetstocompositions(n, k):
    def tau(x):
        if x[1] == 0:
            u = [0] + list(x[0]) + [n+1]
            return (tuple([u[i+1]-u[i]-1 for i in range(k+1)]),1)
        else:
            return (tuple([sum(x[0][:i+1]) + i + 1 for i in range(k)]),0)
    return tau

## toDPP converts sequence of paths to a descending plane partition.
def toDPP(x):
    if x[1] == 0:
        ((A, pi), T) = x[0]
        return (tuple([tuple([T[-i] + 1] + list(filter(lambda q: q > 0,
            [T[-i] - A[-i][j] + j + 2 for j in range(len(A[-i]))]))) for i in range(1,len(T)+1)]), 1)
    else:
        P = x[0]
        R = [list(P[i]) + [0]*(P[i][0] - 1 - len(P[i])) for i in range(len(P))]
        T = tuple(reversed([u[0] - 1 for u in P]))
        pi = tuple(range(1, len(T) + 1))
        A = tuple([tuple([T[i] + 1 - R[-i - 1][j + 1] + j + 1 for j in range(len(R[-i - 1]) - 1)]) for i in range(len(T))])
        return (((A, pi), T), 0)

## trinomial(a, b, c) is the sijection from Problem 3.
def trinomial(a, b, c):
    def tau(x):
        if x[1] == 0:
            A = x[0][0]
            Q = list(set(range(1,a+b+c+1)) - set(A))
            B = tuple(sorted([Q[i-1] for i in x[0][1]]))
            R = list(tuple(set(range(1,a+b+c+1)) - set(A) - set(B)))
            S = list(tuple(set(range(1,a+b+c+1)) - set(B)))
            C = tuple(sorted(filter(lambda i: S[i-1] in R,list(range(1,a+c+1)))))
            return ((B, C),1)
        else:
            B = x[0][0]
            Q = list(set(range(1,a+b+c+1)) - set(B))
            C = [Q[x[0][1][i]-1] for i in range(c)]
            A = tuple(sorted(list(set(Q) - set(C))))
            R = list(tuple(set(range(1,a+b+c+1)) - set(B) - set(C)))
            S = list(tuple(set(range(1,a+b+c+1)) - set(C)))
            Q = list(set(range(1,a+b+c+1)) - set(A))
            B = tuple(sorted(filter(lambda i: Q[i-1] in B,list(range(1,b+c+1)))))
            return ((A, B),0)
    return tau

## ChuVandermond(a, b, c) is the sijection from Problem 4.
def ChuVandermond(a, b, c):
    tau1 = sijdisun(lambda j:
            sijectioncartesian([sijectionidentity,subsetstocompositions(a+c-j-1,a-1)]))
    def tau2(x):
        if x[1] == 0:
            ((J, pi), j) = x[0]
            i = 0
            while i < a and i < b and i+1 not in J and pi[i] == 0:
                i += 1
            if i == a:
                return (tuple([u - a for u in J]), 1)
            elif i == b:
                sigma = pi[b:]
                A = (sijectioncompose([complement(a+c-b-1),
                        subsetstocompositions(a+c-b-1,a-b-1)])((sigma,1)))[0]
                return (A, 1)
            elif i+1 in J:
                Jp = J[1:]
                pip = tuple(list(pi[:i]) + [pi[i] + 1] + list(pi[i+1:]))
                return (((Jp, pip), j - 1), 0)
            elif pi[i] > 0:
                Jp = tuple([i+1] + list(J))
                pip = tuple(list(pi[:i]) + [pi[i] - 1] + list(pi[i+1:]))
                return (((Jp, pip), j + 1), 0)
        else:
            if a >= b:
                A = x[0]
                sigma = (sijectioncompose([complement(a+c-b-1),
                        subsetstocompositions(a+c-b-1,a-b-1)])((A,0)))[0]
                return ((((), tuple([0]*b + list(sigma))), 0), 0)
            else:
                return (((tuple([u+a for u in x[0]]),tuple([0]*a)), c), 0)                
    return sijectioncompose([tau1, tau2])

## Bijsijection(n, i) is the sijection from Problem 5.
def Bisijection(n, i):
    return sijectioncompose([sijdisun(lambda j: sijectioncartesian([sijectionidentity,
            lambda x: ((x[0][:n-1],tuple([r - (n+j-1) for r in x[0][n:]])),1) if x[1] == 0
            else (tuple(list(x[0][0]) + [n+j-1] + [r + (n+j-1) for r in x[0][1]]),0)])),
            sijectiondisjointunion(lambda x: (x[0]-1,1)
                        if x[1] == 0 else (x[0]+1,0), lambda q: sijectionidentity),
            sijdisun(lambda j: sijectioncompose([sijectionprepend,
                    sijectioninverse(sijectionappend)])),
            sijdisun(lambda j: sijectioncartesian([trinomial(n-i-j,n-1,j),sijectionidentity])),
            sijdisun(lambda j: sijectioncompose([sijectionappend,
                    sijectioninverse(sijectionprepend)])),
            sijectioninverse(sijectiondistributivity1),
            sijectioncartesian([sijectionidentity,ChuVandermond(n,n-i,n-1)]),
            sijectioncartesiancommute(0),
            lambda x: ((x[0][:n-1],tuple([r - (n+i-1) for r in x[0][n:]])),0) if x[1] == 1
            else (tuple(list(x[0][0]) + [n+i-1] + [r + (n+i-1) for r in x[0][1]]),1)])

## Bijsijectionprime(n, i) is the same as the sijection Bijsijection(n, i), except that it
## puts the set B_(n, i) on the left.
def Bisijectionprime(n, i):
    def tau(x):
        (((A,p), B), j) = x[0]
        if p == 0:
            y = Bisijection(n,i)((((A, B), j),0))
            if y[1] == 0:
                ((Ap, Bp), jp) = y[0]
                return ((((Ap,0),Bp), jp), 0)
            else:
                return (((((), 1), y[0]), i), 0)
        else:
            ((Ap, Bj), jp) = Bisijection(n,i)((B,1))[0]
            return ((((Ap,0), Bj), jp), 0)
    return tau

## detproduct(m) is the sijection from Problem 6.
def detproduct(m):
    def tau1(x):
        if x[1] == 0:
            pi = x[0][1]
            l = x[0][0]
            return (((tuple([l[i][0][0] for i in range(m)]),tuple([l[i][0][1] for i in range(m)])),
                      (tuple([l[i][1] for i in range(m)]), pi)), 1)
        else:
            return ((tuple([((x[0][0][0][i],x[0][1][0][i]),x[0][0][1][i]) for i in range(m)]),
                     x[0][1][1]), 0)
    def tau2(x):
        if x[1] == 0:
            pi = x[0][1][1]
            l = x[0][1][0]
            if len(set(l)) == m:
                rho = perminverse((l,0))[0]
                return (((x[0][0][0],l),
                         (tuple([x[0][0][1][rho[i]-1] for i in range(m)]),tuple([pi[rho[i]-1] for i in range(m)]))), 1)
            else:
                find = False
                i = 0
                while not(find):
                    j = i + 1
                    while j < len(l) and l[j] != l[i]:
                        j += 1
                    if j == len(l):
                        i += 1
                    else:
                        find = True
                rho = list(pi)
                rho[i] = pi[j]
                rho[j] = pi[i]
                q = list(x[0][0][1])
                q[i] = x[0][0][1][j]
                q[j] = x[0][0][1][i]
                return (((x[0][0][0],l),(tuple(q),tuple(rho))),0)
        else:
            return (((x[0][0][0],x[0][0][1]),(tuple([x[0][1][0][x[0][0][1][i]-1] for i in range(m)]),
                        tuple([x[0][1][1][x[0][0][1][i]-1] for i in range(m)]))), 0)               
    return sijectioncompose([tau1,tau2])

## Cramer(pphi, j) is the sijection from Problem 7 (Cramer's rule).
def Cramer(pphi, j):
    def tau1(x):
        if x[1] == 0:
            ((A, pi), T) = x[0]
            i = pi.index(j) + 1
            return ((tuple(list(A[:i-1]) + [((A[i-1], T), j)] + list(A[i:])), pi), 1)
        else:
            (A, pi) = x[0]
            i = pi.index(j) + 1
            ((B, T), p) = A[i-1]
            if p == j:
                return (((tuple(list(A[:i-1]) + [B] + list(A[i:])), pi), T), 0)
            else:
                q = pi.index(p) + 1
                sigma = list(pi)
                sigma[q-1] = pi[i-1]
                sigma[i-1] = pi[q-1]
                if q < i:
                    A_new = tuple(list(A[:q-1]) + [((A[q-1], T), p)] +
                                  list(A[q:i-1]) + [B] + list(A[i:]))
                else:
                    A_new = tuple(list(A[:i-1]) + [B] +
                                  list(A[i:q-1]) + [((A[q-1], T), p)] + list(A[q:]))
                return ((A_new, tuple(sigma)), 1)
    def rho2(pi):
        i = pi.index(j) + 1
        return sijectioncartesian([sijectionidentity]*(i-1) + [pphi[i-1]] +
                                      [sijectionidentity]*(len(pi)-i))
    tau2 = sijdisun(lambda pi: rho2(pi))
    return sijectioncompose([tau1, tau2])

## solveequation(pphi, i) is the sijection from Problem 8.
def solveequation(pphi, i):
    def tau1(x):
        if x[1] == 0:
            pi = x[0][0][1]
            p = perminverse((pi,0))[0][i-1]
            return (((((x[0][0][0],tuple(list(pi[:p-1]) + list(pi[p:]))), p), x[0][1]),i), 1)
        else:
            j = x[0][1]
            p = x[0][0][0][1]
            pi = x[0][0][0][0][1]
            if i == j:
                return (((x[0][0][0][0][0],tuple(list(pi[:p-1]) + [j] + list(pi[p-1:]))),x[0][0][1]), 0)
            else:
                q = pi.index(j) + 1
                if q >= p:
                    q += 1
                l = list(pi[:p-1]) + [j] + list(pi[p-1:])
                rho = tuple(l[:q-1] + l[q:])
                return (((((x[0][0][0][0][0], rho), q), x[0][0][1]), j), 1)
    def tau2(x):
        if x[1] == 0:
            j = x[0][1]
            p = x[0][0][0][1]
            pi = x[0][0][0][0][1]
            l = x[0][0][0][0][0]
            return ((((tuple(list(l[:p-1]) + list(l[p:])), pi), ((l[p-1], x[0][0][1]), j)), p), 1)
        else:
            p = x[0][1]
            j = x[0][0][1][1]
            l = x[0][0][0][0]
            return (((((tuple(list(l[:p-1]) + [x[0][0][1][0][0]] + list(l[p-1:])), x[0][0][0][1]),p), x[0][0][1][0][1]), j), 0)
        return x
    return sijectioncompose([tau1, tau2,
            sijdisun(lambda p: sijectioncartesian([sijectionidentity, pphi[p-1]]))])

## elementary_aux(kk, j) is the auxilliary sijection that appears in the construction of Problem 9.
def elementary_aux(kk, j):
    n = len(kk)
    if n == 1:
        def tau(x):
            if x[0][0][1] == ():
                return (((x[0][0][0],x[0][1]),x[0][1]), 0)
            else:
                return (((x[0][0][0],()),x[0][1]), 0)
        return tau
    def psi1(kk,U,i):
        e = [1 if j+1 in U else 0 for j in range(n)]
        return sijectioncompose(
                [alpha(kk[i]+e[i], kk[i]-1, kk[i+1]+e[i+1]),
                sijectiondisjointunion2(sijectionidentity,
                alpha(kk[i], kk[i+1], kk[i+1]+e[i+1])),
                sijectiondisjointunionassociativity(1)])
    tau1 = sijdisun(lambda V: sijdisun(lambda U:
                sijectiondisjointunion(sijectioncartesian([psi1(kk,U,i) for i in range(n-1)]),
                    lambda x: sijectionidentity)))
    def tau2(x):
        if x[1] == 0:
            U = x[0][0][1]
            V = x[0][1]
            a = [x[0][0][0][1][i][1] for i in range(len(x[0][0][0][1]))]
            i = 0
            while i < n and (i+1 not in V or
                             i == 0 and a[i] == 0 or
                             0 < i < n-1 and (a[i-1] == 2 or a[i] == 0) or
                             i == n-1 and a[i-1] == 2):
                i += 1
            if i < n:
                Up = (tuple(sorted(list(U) + [i+1]))) if i+1 not in U else (tuple(sorted(list(set(U) - {i+1,}))))
                return (((x[0][0][0], Up), x[0][1]), 0)
            else:
                return (x[0], 1)
        else:
            return (x[0], 0)
    def tau3(x):
        if x[1] == 0:
            l = x[0][1]
            V = x[0][0][1]
            U = x[0][0][0][1]
            e = [1 if i+1 in U else 0 for i in range(n-1)]
            return ((((x[0][0][0][0],tuple([l[i] + e[i] for i in range(n-1)])),U),V),1)
        else:
            V = x[0][1]
            U = x[0][0][1]
            e = [1 if i+1 in U else 0 for i in range(n-1)]
            l = x[0][0][0][1]
            return ((((x[0][0][0][0],U),V),tuple([l[i] - e[i] for i in range(n-1)])),0)
    def psi2(kk,U,i):
        e = [1 if j+1 in U else 0 for j in range(n-1)]
        return sijectioncompose(
                [alpha(kk[i]+e[i], kk[i]-1, kk[i+1]+e[i]),
                sijectiondisjointunion2(sijectionidentity,
                alpha(kk[i], kk[i+1], kk[i+1]+e[i])),
                sijectiondisjointunionassociativity(1)])
    tau4 = sijdisun(lambda V: sijdisun(lambda U:
                sijectiondisjointunion(sijectioncartesian([psi2(kk,U,i) for i in range(n-1)]),
                    lambda x: sijectionidentity)))
    def tau5(x):
        if x[1] == 0:
            U = x[0][0][1]
            V = x[0][1]
            a = [x[0][0][0][1][i][1] for i in range(len(x[0][0][0][1]))]
            i = 0
            while i < n-1 and (i+1 not in V or a[i] != 1):
                i += 1
            if i < n-1:
                Up = (tuple(sorted(list(U) + [i+1]))) if i+1 not in U else (tuple(sorted(list(set(U) - {i+1,}))))
                return (((x[0][0][0], Up), x[0][1]), 0)
            else:
                return (x[0], 1)
        else:
            return (x[0], 0)
    def tau6(x):
        if x[1] == 0:
            U = x[0][0][1]
            a = x[0][0][0][1]
            Up = tuple([(U[i] if a[U[i]-1][1] == 0 else U[i] + 1) for i in range(len(U))])
            return (((x[0][0][0],Up),Up), 1)
        else:
            U = x[0][0][1]
            a = x[0][0][0][1]
            Up = tuple([U[i] if (U[i] <= len(a) and a[U[i]-1][1] == 0) else U[i] - 1 for i in range(len(U))])
            return (((x[0][0][0],Up),Up), 0)
    return sijectioncompose([tau1,tau2,sijectioninverse(tau6),sijectioninverse(tau5),
                             sijectioninverse(tau4),sijectioninverse(tau3)])    

## elementary1(kk, j) is the first sijection from Problem 9.
def elementary1(kk, j):
    return sijectioncompose([elementary_aux(kk, j), sijdisun(lambda ll: elementary1(ll, j))])

## elementary2(kk, j) is the second sijection from Problem 9.
def elementary2(kk, j):
    n = len(kk)
    def tau(x):
        if x[0] == ():
            return (x[0],1-x[1])
        else:
            y = tau((x[0][0],x[1]))
            return ((y[0],tuple([-x[0][1][-i-1] for i in range(len(x[0][1]))])),y[1])
    def psi(x):
        return (((tau((x[0][0][0],0))[0],tuple(reversed([n+1-i for i in x[0][0][1]]))),
                 tuple(reversed([n+1-i for i in x[0][1]]))),1-x[1])
    kkp = tuple([-kk[-i-1] for i in range(len(kk))])
    return sijectioncompose([psi, elementary1(kkp, j), psi])

## elementary1prime_aux(kk, j) is an auxiliarly sijection that appears in Problem 10.
def elementary1prime_aux(kk, j):
    def tau1(x):
        if x[1] == 0:
            if x[0][1] == 0:
                return (x[0][0], 1)
            else:
                return (x[0][0][0], 1)
        else:
            V = x[0][1]
            U = x[0][0][1]
            if 1 not in V:
                return ((x[0], 0), 0)
            else:
                if 1 in U:
                    return (((x[0], 0), 1), 0)
                else:
                    return (((x[0], 1), 1), 0)
    def tau2(x):
        V = x[0][0][1]
        U = x[0][0][0][1]
        if x[1] == 0:
            if x[0][1] == 0:
                return ((((x[0][0][0][0],U[1:]),V[1:]),0),1)
            else:
                return ((((x[0][0][0][0],U),V[1:]),1),1)
        else:
            if x[0][1] == 0:
                return ((((x[0][0][0][0],tuple([1] + list(U))),tuple([1] + list(V))),0),0)
            else:
                return ((((x[0][0][0][0],U),tuple([1] + list(V))),1),0)
    return sijectioncompose([fromsijectiontoempty(sijectioncompose([tau1,elementary1(kk,j)])),tau2])

## elementary2prime_aux(kk, j) is an auxiliarly sijection that appears in Problem 10.
def elementary2prime_aux(kk, j):
    def tau1(x):
        if x[1] == 0:
            if x[0][1] == 0:
                return (x[0][0], 1)
            else:
                return (x[0][0][0], 1)
        else:
            V = x[0][1]
            U = x[0][0][1]
            if 1 not in V:
                return ((x[0], 0), 0)
            else:
                if 1 in U:
                    return (((x[0], 0), 1), 0)
                else:
                    return (((x[0], 1), 1), 0)
    def tau2(x):
        V = x[0][0][1]
        U = x[0][0][0][1]
        if x[1] == 0:
            if x[0][1] == 0:
                return ((((x[0][0][0][0],U[1:]),V[1:]),0),1)
            else:
                return ((((x[0][0][0][0],U),V[1:]),1),1)
        else:
            if x[0][1] == 0:
                return ((((x[0][0][0][0],tuple([1] + list(U))),tuple([1] + list(V))),0),0)
            else:
                return ((((x[0][0][0][0],U),tuple([1] + list(V))),1),0)
    return sijectioncompose([fromsijectiontoempty(sijectioncompose([tau1,elementary2(kk,j)])),tau2])

## elementary1prime(kk, j) is the first sijection from Problem 10.
def elementary1prime(kk, j):
    if j == 0:
        def tau(x):
            if x[1] == 0:
                return ((((),x[0][0][0]), 0), 1)
            else:
                return (((x[0][0][1], ()), ()), 0)
        return tau
    if j == 1:
        def tau(x):
            if x[1] == 0:
                if x[0][1] == 0:
                    return ((((1,),x[0][0][0][0]), 1), 1)
                else:
                    return ((((),x[0][0][0][0]), 0), 1)
            else:
                if x[0][1] == 0:
                    return ((((x[0][0][1], ()), ()), 1), 0)
                else:
                    return ((((x[0][0][1], ()), ()), 0), 0)       
        return sijectioncompose([elementary1prime_aux(kk, j), tau])
    else:
        def tau(x):
            if x[1] == 0:
                if x[0][1] == 0:
                    return (((tuple(list(x[0][0][0][0]) + [j]), x[0][0][0][1]), x[0][0][1]+1), 1)
                else:
                    return (x[0][0], 1)
            else:
                if j in x[0][0][0]:
                    return ((((x[0][0][0][:-1], x[0][0][1]), x[0][1] - 1), 0), 0)
                else:
                    return ((x[0], 1), 0)
        return sijectioncompose([elementary1prime_aux(kk, j),sijectiondisjointunion2(
            elementary1prime(tuple([kk[0]+1] + list(kk[1:])),j-1), elementary1prime(kk,j-1)), tau])

## elementary2prime(kk, j) is the second sijection from Problem 10.
def elementary2prime(kk, j):
    if j == 0:
        def tau(x):
            if x[1] == 0:
                return ((((),x[0][0][0]), 0), 1)
            else:
                return (((x[0][0][1], ()), ()), 0)
        return tau
    if j == 1:
        def tau(x):
            if x[1] == 0:
                if x[0][1] == 0:
                    return ((((1,),x[0][0][0][0]), 1), 1)
                else:
                    return ((((),x[0][0][0][0]), 0), 1)
            else:
                if x[0][1] == 0:
                    return ((((x[0][0][1], ()), ()), 1), 0)
                else:
                    return ((((x[0][0][1], ()), ()), 0), 0)       
        return sijectioncompose([elementary2prime_aux(kk, j), tau])
    else:
        def tau(x):
            if x[1] == 0:
                if x[0][1] == 0:
                    return (((tuple(list(x[0][0][0][0]) + [j]), x[0][0][0][1]), x[0][0][1]+1), 1)
                else:
                    return (x[0][0], 1)
            else:
                if j in x[0][0][0]:
                    return ((((x[0][0][0][:-1], x[0][0][1]), x[0][1] - 1), 0), 0)
                else:
                    return ((x[0], 1), 0)
        return sijectioncompose([elementary2prime_aux(kk, j),sijectiondisjointunion2(
            elementary2prime(tuple([kk[0]-1] + list(kk[1:])),j-1), elementary2prime(kk,j-1)), tau])

## lefttoright(kk, Tp) is the sijection from Problem 11.
def lefttoright(kk, Tp):
    n = len(kk)
    def tau1(x):
        if x[1] == 0:
            mu = x[0][1]
            T = x[0][0]
            r = tuple([sum([1 if mu[j] <= 0 else 0 for j in range(n-1)])] +
                      [1 if mu[j] >= 0 else 0 for j in range(n-1)])
            B = list(filter(lambda i: mu[i-1] >= 0, range(1,n)))
            A = tuple(filter(lambda i: mu[B[i-1]-1] == 1, range(1,len(B)+1)))
            return (((A,T), r), 1)
        else:
            ((A,T), r) = x[0]
            B = list(filter(lambda i: r[i] == 1, range(1,n)))
            C = [B[i-1] for i in A]
            mu = tuple([1 if i+1 in C else (0 if i+1 in B else -1) for i in range(n-1)])
            return ((T,mu), 0)
    tau2 = sijdisun(lambda r: sijectioncartesian(
        [ChuVandermond(r[0]+1,n-1-sum(r[1:]),n-r[0]-1),sijectionidentity]))
    def tau3(x):
        if x[1] == 0:
            (((A, ((T, U), V)), i), j) = x[0]
            epsilon = [1 if p+2 in U else 0 for p in range(n-1)]
            R = list(filter(lambda p: p not in U, range(2,n+1)))
            P = tuple(filter(lambda p: R[p-1] not in V,range(1,len(R)+1)))
            return (((((P, A),j), T), tuple([i] + epsilon)), 1)
        else:
            ((((P, A),j), T), r) = x[0]
            i = r[0]
            U = tuple(filter(lambda p: r[p-1] == 1,range(2,n+1)))
            R = list(filter(lambda p: p not in U, range(2,n+1)))
            Pp = list(filter(lambda p: p not in P,range(1,len(R)+1)))
            V = tuple(sorted(list(U) + [R[p-1] for p in Pp]))
            return ((((A, ((T, U), V)), i), j), 0)
    def tau4(x):
        return sijdisun(lambda j: sijdisun(lambda i:
                    sijectioncartesian([sijectionidentity,
                        elementary2prime(tuple([kk[0] + i] +
                          [kk[p+1] + c(Tp,n-1,p+1) for p in range(n-1)]),n-1-j)])))(x)
    def tau5(x):
        ((((A,((B,T),p)),i)), j) = x[0]
        return (((((B,((A,T),i)),p)), j), 1 - x[1])
    def tau6(x):
        return sijdisun(lambda j: sijdisun(lambda i:
                    sijectioncartesian([sijectionidentity,
                        elementary1prime(tuple([kk[0] - i] +
                          [kk[p+1] + c(Tp,n-1,p+1) for p in range(n-1)]),n-1-j)])))(x)
    tau7 = tau3
    tau8 = sijdisun(lambda r: sijectioncartesian(
        [ChuVandermond(r[0]+1,n-1-sum(r[1:]),n-r[0]-1),sijectionidentity]))
    def tau9(x):
        if x[1] == 0:
            mu = x[0][1]
            T = x[0][0]
            r = tuple([sum([1 if mu[j] >= 0 else 0 for j in range(n-1)])] +
                      [1 if mu[j] <= 0 else 0 for j in range(n-1)])
            B = list(filter(lambda i: mu[i-1] <= 0, range(1,n)))
            A = tuple(filter(lambda i: mu[B[i-1]-1] == -1, range(1,len(B)+1)))
            return (((A,T), r), 1)
        else:
            ((A,T), r) = x[0]
            B = list(filter(lambda i: r[i] == 1, range(1,n)))
            C = [B[i-1] for i in A]
            mu = tuple([-1 if i+1 in C else (0 if i+1 in B else 1) for i in range(n-1)])
            return ((T,mu), 0)    
    return sijectioncompose([tau1, sijectioninverse(tau2), sijectioninverse(tau3),tau4,
            tau5, sijectioninverse(tau6), tau7, tau8, sijectioninverse(tau9)])

## rotation(kk, par) is the sijection from Problem 12 (rotation of monotone triangles).
def rotation(kk, par):
    n = len(kk)
    def tau1(x):
        if x[1] == 0:
            (A, T) = x[0]
            f = APlisttoarray(T,n)
            mu = tuple([f(1,i+2) for i in range(n-1)])
            Tp = AParraytolist(lambda i,j: f(i+1,j+1), n-1)
            return (((A, mu), Tp), 1)
        else:
            ((A, mu), Tp) = x[0]
            f = APlisttoarray(Tp, n-1)
            T = AParraytolist(lambda i,j: mu[j-2] if i == 1 else f(i-1,j-1),n)
            return ((A,T), 0)
    def tau2(kk,Tp,mu):
        def psi(x):
            if x[0][0] == ():
                return (((),(x[0][1][0] + (-1 if x[1] == 0 else 1),)),1-x[1])
            else:
                return ((psi((x[0][0],x[1]))[0],
                    tuple([x[0][1][i] + (-1 if x[1] == 0 else 1)
                           for i in range(len(x[0][1]))])),1-x[1])
        T = addright(Tp,mu,n)
        l = tuple([kk[0] + c(T,n,n)] + list([kk[i+1] + c(T,n,i+1) for i in range(n-1)]))
        return sijectioncompose([pi(tuple([l[i] + 1 for j in range(i)] + [l[0]-i] + [l[i+j+1]
            for j in range(n-i-1)]), i+1) for i in range(n-1)] + [psi])
    def tau3(x):
        if x[1] == 0:
            (A, T) = x[0]
            f = APlisttoarray(T,n)
            mu = tuple([f(i+1,n) for i in range(n-1)])
            Tp = AParraytolist(f, n-1)
            return (((A, mu), Tp), 1)
        else:
            ((A, mu), Tp) = x[0]
            f = APlisttoarray(Tp, n-1)
            T = AParraytolist(lambda i,j: mu[i-1] if j == n else f(i,j),n)
            return ((A,T), 0)
    
    return sijectioncompose([Gamma(kk, par),
                             tau1,
                             sijdisun(lambda Tp: lefttoright(kk, Tp)),
                             sijdisun(lambda Tp:
                                sijdisun(lambda mu: tau2(kk,Tp,mu))),
                             sijectioninverse(tau3),
                             sijectioninverse(Gamma(rot(kk), par))])

## fromMTsubi(kk, i) is the first sijection from Problem 13.
def fromMTsubi(kk, i):
    if i == 1:
        def tau(x):
            if x[1] == 0:
                return ((((),tuple(list(x[0][:-1]) + [tuple([x[0][-1][0] + 1]
                                               + list(x[0][-1][1:]))])), 0), 1)
            else:
                return (tuple(list(x[0][0][1][:-1]) + [tuple([x[0][0][1][-1][0] - 1]
                                + list(x[0][0][1][-1][1:]))]), 0)                
        return tau
    elif len(kk) == 1:
        def tau(x):
            ((A, T), j) = x[0]
            if i-1 not in A:
                Ap = tuple(list(A) + [i-1])
                Tp = ((T[0][0]+1,),)
                jp = j + 1
            else:
                Ap = A[:-1]
                Tp = ((T[0][0]-1,),)
                jp = j - 1
            return (((Ap, Tp), jp), 1)
        return tau            
    else:
        def tau1(x):
            if x[1] == 0:
                A = x[0]
                return ((A[:-1], A[-2][1:]), 1)
            else:
                (A, l) = x[0]
                return (tuple(list(A) + [kk]), 0)
        tau2 = sijdisun(lambda l: fromMTsubi(tuple([kk[0]] + list(l)),i-1))
        def tau3(x):
            if x[1] == 0:
                (((A, T), p), l) = x[0]
                if (kk[0] + p + 1 < kk[1] or kk[0] + p + 1 == kk[1] and (l == () or kk[1] < l[0])):
                    return (((A, tuple(list(T) + [tuple([kk[0]+p+1]+list(kk[1:]))])), p), 1)
                elif (kk[0] + p + 1 > kk[1] or kk[0] + p + 1 == kk[1] == l[0]):
                    return (((tuple(list(A) + [i-1]), tuple(list(T) +
                                    [tuple([kk[0]+p+2] + list(kk[1:]))])), p+1), 1)                
            else:
                ((A, T), j) = x[0]
                l = T[-2][1:]
                p = T[-2][0] - kk[0] - 1
                if (kk[0] + p + 1 < kk[1] or kk[0] + p + 1 == kk[1] and (l == () or kk[1] < l[0])) and (len(A) == p and i-1 not in A):
                    return ((((A, T[:-1]), p), l), 0)
                elif (kk[0] + p + 1 > kk[1] or kk[0] + p + 1 == kk[1] and (l != () and kk[1] == l[0])) and (len(A) == p+1 and i-1 in A):
                    return ((((A[:-1], T[:-1]), p), l), 0)
                else:
                    if i-1 not in A:
                        Ap = tuple(list(A) + [i-1])
                        Tp = tuple(list(T[:-1]) + [tuple([T[-1][0]+1] + list(T[-1][1:]))])
                        jp = j + 1
                    else:
                        Ap = A[:-1]
                        Tp = tuple(list(T[:-1]) + [tuple([T[-1][0]-1] + list(T[-1][1:]))])
                        jp = j - 1
                    return (((Ap, Tp), jp), 1)
        return sijectioncompose([tau1, tau2, tau3])

## fromMTsupi(kk, i) is the second sijection from Problem 13.
def fromMTsupi(kk,i):
    if i == 1:
        def tau(x):
            if x[1] == 0:
                return ((((),tuple(list(x[0][:-1]) + [tuple(
                                    list(x[0][-1][:-1]) + [x[0][-1][-1] - 1])])), 0), 1)
            else:
                return (tuple(list(x[0][0][1][:-1]) + [tuple(
                                list(x[0][0][1][-1][:-1]) + [x[0][0][1][-1][-1] + 1])]), 0)                
        return tau
    elif len(kk) == 1:
        def tau(x):
            ((A, T), j) = x[0]
            if i-1 not in A:
                Ap = tuple(list(A) + [i-1])
                Tp = ((T[0][0]-1,),)
                jp = j + 1
            else:
                Ap = A[:-1]
                Tp = ((T[0][0]+1,),)
                jp = j - 1
            return (((Ap, Tp), jp), 1)
        return tau            
    else:
        def tau1(x):
            if x[1] == 0:
                A = x[0]
                return ((A[:-1], A[-2][:-1]), 1)
            else:
                (A, l) = x[0]
                return (tuple(list(A) + [kk]), 0)
        tau2 = sijdisun(lambda l: fromMTsupi(tuple(list(l) + [kk[-1]]),i-1))
        def tau3(x):
            if x[1] == 0:
                (((A, T), p), l) = x[0]
                if (kk[-1] - p - 1 > kk[-2] or kk[-1] - p - 1 == kk[-2] and (l == () or kk[-2] > l[-1])):
                    return (((A, tuple(list(T) + [tuple(list(kk[:-1])+[kk[-1]-p-1])])), p), 1)
                elif (kk[-1] - p - 1 < kk[-2] or kk[-1] - p - 1 == kk[-2] == l[-1]):
                    return (((tuple(list(A) + [i-1]), tuple(list(T) +
                                    [tuple(list(kk[:-1])+[kk[-1]-p-2])])), p+1), 1)                
            else:
                ((A, T), j) = x[0]
                l = T[-2][:-1]
                p = kk[-1] - 1 - T[-2][-1]
                if (kk[-1] - p - 1 > kk[-2] or kk[-1] - p - 1 == kk[-2] and (l == () or kk[-2] > l[-1])) and (len(A) == p and i-1 not in A):
                    return ((((A, T[:-1]), p), l), 0)
                elif (kk[-1] - p - 1 < kk[-2] or kk[-1] - p - 1 == kk[-2] and (l != () and kk[-2] == l[-1])) and (len(A) == p+1 and i-1 in A):
                    return ((((A[:-1], T[:-1]), p), l), 0)
                else:
                    if i-1 not in A:
                        Ap = tuple(list(A) + [i-1])
                        Tp = tuple(list(T[:-1]) + [tuple(list(T[-1][:-1])+[T[-1][-1]-1])])
                        jp = j + 1
                    else:
                        Ap = A[:-1]
                        Tp = tuple(list(T[:-1]) + [tuple(list(T[-1][:-1])+[T[-1][-1]+1])])
                        jp = j - 1
                    return (((Ap, Tp), jp), 1)
        return sijectioncompose([tau1, tau2, tau3])

## Aisijection(n, i, par) is the sijection from Problem 14.
def Aisijection(n, i, par):
    def tau1(x):
        ((A, T), j) = x[0]
        Tp = tuple([tuple(reversed(list(T[p]))) for p in range(n)])
        jp = n + 1 - j
        return (((A, Tp), jp), 1-x[1])
    def tau2(x):
        ((A, T), j) = x[0]
        Ap = tuple(filter(lambda k: k not in A,range(1,2*n-i)))
        jp = 2*n - j - 1
        return (((Ap, T), jp), 1-x[1])
    def tau3(x):
        ((A, T), j) = x[0]
        if x[1] == 0:
            Tp = tuple([tuple([T[q][n-1-p] for q in range(n)]) for p in range(n)])
        else:
            Tp = tuple([tuple([T[n-1-q][p] for q in range(n)]) for p in range(n)])
        return (((A, Tp), j), 1-x[1])
    tau4 = sijdisun(lambda j: sijectioncartesian([sijectionidentity,
                                                      sijectioninverse(MTtoASM)]))
    tau5 = sijdisun(lambda j: sijectioncartesian([sijectionidentity,
                                        fromMTsubi(tuple(range(1,n+1)),2*n-j-1)]))
    def tau6(x):
        if x[1] == 0:
            ((A, ((B, T), p)), j) = x[0]
            return (((((A, B), j), T), p), 1)
        else:
            ((((A, B), j), T), p) = x[0]
            return (((A, ((B, T), p)), j), 0)
    tau7 = sijdisun(lambda p: sijectioncartesian([
        ChuVandermond(p + 1, 2 * n - i - 1, 2*n - p - 2), sijectionidentity]))
    def tau8(x):
        ((A, T), p) = x[0]
        pp = 2*n - p - 2
        return (((A, T), pp), 1-x[1])
    tau9 = sijdisun(lambda p: sijectioncartesian([sijectionidentity,
                                        rotation(tuple([2*n-p] + list(range(2,n+1))), par)])) 
    def tau10(x):
        ((A, T), p) = x[0]
        Tp = tuple([tuple([T[a][b] + (-1 if x[1] == 0 else 1) for b in range(len(T[a]))])
                    for a in range(len(T))])
        return (((A, Tp), p), 1-x[1])
    tau11 = sijectioninverse(fromMTsupi(tuple(range(1,n+1)), i))
    tau12 = MTtoASM
    def tau13(x):
        T = x[0]
        Tp = tuple([tuple([T[n-1-q][n-1-p] for q in range(n)]) for p in range(n)])
        return (Tp, 1-x[1])
    return sijectioncompose([tau1,tau2,tau3,tau4,tau5,tau6,tau7,
                             tau8,tau9,tau10,tau11,tau12,tau13])

## Aisijectionprime(n, i, par) is like Aisijection, but it puts A_(n, i) on the LHS.        
def Aisijectionprime(n, i, par):
    def tau(x):
        (((A,p), B), j) = x[0]
        if p == 0:
            y = Aisijection(n,i,par)((((A, B), j),0))
            if y[1] == 0:
                ((Ap, Bp), jp) = y[0]
                return ((((Ap,0),Bp), jp), 0)
            else:
                return (((((), 1), y[0]), i), 0)
        else:
            ((Ap, Bj), jp) = Aisijection(n,i,par)((B,1))[0]
            return ((((Ap,0), Bj), jp), 0)
    return tau

## AiBiequation(n, i, par) is the auxiliary sijection
## \sqcup P x (B x A \sqcup -A x B) constructed for sijection in Problem 1
def AiBiequation(n, i, par):
    def tau1(x):
        if x[1] == 0:
            return (x[0], 1)
        else:
            ((C, ((A, B), p)), j) = x[0]
            if j > 0:
                return (x[0], 0)
            else:
                return (((C, ((B, A), 1-p)), j), 1)
    def tau2(x):
        if x[1] == 0:
            ((C, ((B, A), p)), j) = x[0]
            return (((B, ((C, A), j + 1)), p), 1)
        else:
            ((B, ((C, A), j)), p) = x[0]
            return (((C, ((B, A), p)), j - 1), 0)
    tau3 = sijectiondisjointunion2(
                sijectioncartesian([sijectionidentity,Aisijectionprime(n, i, par)]),
                sijectioncartesian([sijectionidentity,Bisijectionprime(n, i)]))        
    return sijectioncompose([tau1,tau2,tau3])

## find_points(T, path) converts a set of subsets to paths.
def find_points(T, path):
    (U, pi) = path
    points = [[]]*len(T)
    for i in range(len(T)):
        x = 0
        y = - T[i] - 1
        points[i] = [(x, y)]
        for j in range(1, T[i] + T[pi[i] - 1] + 1):
            if j in U[i]:
                x += 1
            else:
                y += 1
            points[i] += [(x, y)]
    return points

## nonintersecting(T, S) selects non-intersecting paths in signed set S.
def nonintersecting(T, S):
    def nonintersectingQ(U, path):
        points = find_points(U, path)
        m = len(U)
        return all([set(points[i]).isdisjoint(set(points[j]))
          for i in range(m - 1) for j in range(i + 1, m)])
    return (list(filter(lambda path: nonintersectingQ(T, path), S[0])),
            list(filter(lambda path: nonintersectingQ(T, path), S[1])))             

## fromdet(n) is the sijection from Problem 15.
def fromdet(n):
    def tau1(x):
        if x[1] == 0:
            return ((x[0][0][:-1], x[0][1][:-1]), 1)
        else:
            return ((tuple(list(x[0][0]) + [((), 1)]), tuple(list(x[0][1]) + [n-1])), 0)
    def tau2(x):
        if x[1] == 0:
            return (((tuple([() for i in range(n-2)]), tuple(range(1,n-1))), x[0]), 1)
        else:
            return (x[0][1], 0)
    tau3 = sijectioninverse(detproduct(n - 2))
    def psi4(pi, p):
        def rho4(x):
            if x[1] == 0:
                ((A, (B, q)), k)  = x[0]
                if q == 1:
                    return ((A, 1), 1)
                else:
                    Bc = complement(2*n - k - 2)((B, 0))[0]
                    t = ChuVandermond(n + pi[p], n, n - (p + 1) - pi[p] - 1)((((A, Bc), k - p - 1), 0))
                    if t[1] == 0:
                        ((A_new, B_newc), k_new) = t[0]
                        B_new = complement(2*n - k_new - p - 1 - 2)((B_newc, 0))[0]
                        return (((A_new, (B_new, 0)), k_new + p + 1), 0)
                    else:
                        A_newc = t[0]
                        A_new = complement(n - p - 1 - 2)((A_newc, 0))[0]
                        return ((A_new, 0), 1)
            else:
                (A, q) = x[0]
                if q == 1:
                    return (((A, ((), 1)), pi[p]), 0)
                else:
                    Ac = complement(n - p - 1 - 2)((A, 0))[0]
                    ((A_new, B_newc), k_new) = ChuVandermond(n + pi[p], n, n - (p + 1) - pi[p] - 1)((Ac, 1))[0]
                    B_new = complement(2*n - k_new - p - 1 - 2)((B_newc, 0))[0]
                    return (((A_new, (B_new, 0)), k_new + p + 1), 0)
        return rho4
    tau4 = sijdisun(lambda pi: sijectioncartesian([psi4(pi, p) for p in range(n - 2)]))
    def psi5(pi, p):
        def rho5(x):
            if x[1] == 0:
                (A, q) = x[0]
                if q == 1:
                    return (((((), 1), A), p + 1), 1)
                else:
                    ((A_new, B_newc), k_new) = ChuVandermond(p + 1 + 2, n, pi[p] - 1)((A, 1))[0]
                    B_new = complement(p + 1 + pi[p] - k_new)((B_newc, 0))[0]
                    return ((((B_new, 0), A_new), pi[p] - k_new), 1)
            else:
                (((B, q), A), k)  = x[0]
                if q == 1:
                    return ((A, 1), 0)
                else:
                    Bc = complement(p + 1 + k)((B, 0))[0]
                    t = ChuVandermond(p + 1 + 2, n, pi[p] - 1)((((A, Bc), pi[p] - k), 0))
                    if t[1] == 0:
                        ((A_new, B_newc), k_new) = t[0]
                        B_new = complement(p + 1 + pi[p] - k_new)((B_newc, 0))[0]
                        return ((((B_new, 0), A_new), pi[p] - k_new), 1)
                    else:
                        A_new = t[0]
                        return ((A_new, 0), 0)
        return rho5
    tau5 = sijdisun(lambda pi: sijectioncartesian([psi5(pi, p) for p in range(n - 2)]))
    tau6 = detproduct(n - 2)
    def tau7(x):
        if x[1] == 0:
            return (x[0][0], 1)
        else:
            return ((x[0], (tuple([() for i in range(n-2)]), tuple(range(1,n-1)))), 0)
    def tau8(x):
        if x[1] == 0:
            (u, pi) = x[0]
            T = tuple(filter(lambda i: pi[i - 1] == i and u[i - 1][1] == 1, range(1, n - 1)))
            U = complement(n - 2)((T,0))[0]
            sigma = [pi[i - 1] for i in U]
            pi_new = tuple([U.index(pi[i - 1]) + 1 for i in U])
            u_new = tuple([u[i - 1][0] for i in U])
            return (((u_new, pi_new), U), 1)
        else:
            ((u, pi), U) = x[0]
            sigma = [U[pi[i] - 1] for i in range(len(U))]
            pi_new = list(range(1, n - 1))
            u_new = [((), 1)]*(n - 2)
            j = 0
            for i in range(n - 2):
                if i + 1 in U:
                    pi_new[i] = sigma[j]
                    u_new[i] = (u[j], 0)
                    j += 1
            return ((tuple(u_new), tuple(pi_new)), 0)
    def tau9(x): # Gessel-Viennot
        if x[1] == 0:
            ((U, pi), T) = x[0]
            m = len(T)
            points = find_points(T, (U, pi))
            intersections = list(filter(lambda ij: not(set(points[ij[0]]).isdisjoint(set(points[ij[1]]))),
                         [(i, j) for i in range(m - 1) for j in range(i + 1, m)]))
            if intersections == []:
                return (x[0], 1)
            else:
                i = intersections[0][0]
                p = 0
                while all([points[i][p] not in points[q] for q in range(i + 1, m)]):
                    p += 1
                j = i + 1
                while points[i][p] not in points[j]:
                    j += 1
                q = points[j].index(points[i][p])
                pointsi = points[i]
                points[i] = points[i][:p] + points[j][q:]
                points[j] = points[j][:q] + pointsi[p:]
                Ui = tuple(filter(lambda p: points[i][p][0] > points[i][p - 1][0],
                                  range(1, len(points[i]))))
                Uj = tuple(filter(lambda p: points[j][p][0] > points[j][p - 1][0],
                                  range(1, len(points[j]))))
                U_new = tuple(list(U[:i]) + [Ui] + list(U[i + 1: j]) + [Uj] + list(U[j + 1:]))
                pi_new = tuple(list(pi[:i]) + [pi[j]] + list(pi[i + 1: j]) + [pi[i]] + list(pi[j + 1:]))
                return (((U_new, pi_new), T), 0)
        else:
            return (x[0], 0)
    tau10 = toDPP
    return sijectioncompose([tau1, tau2, tau3, tau4, tau5, tau6, tau7, tau8, tau9, tau10])

## MainBijection(n, i, par) is the sijection from Problem 1
def MainBijection(n, i, par):
    return fromsijectiontoempty(sijectioncompose([sijectiondisjointunion2(sijectioninverse(sijectionprepend),
                        sijectioninverse(sijectionprepend)),
                        sijectioninverse(sijectiondistributivity1),
                        sijectioncartesian([sijectioninverse(fromdet(n)), sijectionidentity]),
                        solveequation(tuple([AiBiequation(n, j + 2, par) for j in range(n-1)]), i - 1)]))

## fromdet2(n, k) is the determinantal evaluation for Problem 2.
def fromdet2(n, k):
    def tau1(x):
        if x[1] == 0:
            (A, pi) = x[0]
            p = pi.index(k-1)
            return (((tuple(list([(A[i], 0) for i in range(p)]) + [(A[p], 1)]
                            + list([(A[i], 0) for i in range(p+1,len(A))])), pi), 0), 1)
        else:
            ((A, pi), q) = x[0]
            p = pi.index(k-1)
            if q == 1:
                return (((tuple(list([(A[i], 0) for i in range(len(A))])), pi), 0), 1)
            else:
                if A[p][1] == 0:
                    return (((tuple([A[i][0] for i in range(len(A))]), pi), 1), 1)
                else:
                    return ((tuple([A[i][0] for i in range(len(A))]), pi), 0)
    def tau2(x):
        w = (tuple([()]*(n-1)), tuple(range(1, n)))
        if x[1] == 0:
            ((A, pi), q) = x[0]
            return (((w, (A, pi)), q), 1)
        else:
            ((y, (A, pi)), q) = x[0]
            return (((A, pi), q), 0)
    tau3 = sijectiondisjointunion2(sijectioninverse(detproduct(n - 1)), sijectioninverse(detproduct(n - 1)))
    def psi4(x):
        if x[1] == 0:
            ((A, (B, p)), k) = x[0]
            return ((((A, B), k), p), 1)
        else:
            (((A, B), k), p) = x[0]
            return (((A, (B, p)), k), 0)
    tau4 = sijectiondisjointunion2(sijdisun(lambda pi: sijectioncartesian([psi4]*(n-1))), sijectionidentity)
    def rho5a(p, q):
        if p == q == n - 2:
            return (lambda x: ((((), 1),1) if x[1] == 0 else ((((), ((), 1)), n-1),0)))
        def psi(x):
            if x[1] == 0:
                ((A, (B, m)), l) = x[0]
                if m == 1:
                    return ((A, 1), 1)
                else:
                    Bp = complement(2*n-(l-1)-3)((B,0))[0]
                    C = ChuVandermond(n+q+1,n,n-p-q-3)((((A,Bp),(l-1)-p),0))
                    if C[1] == 0:
                        ((A_new, Bp_new), l_new) = C[0]
                        B_new = complement(2*n-(l_new)-p-3)((Bp_new,0))[0]
                        return (((A_new, (B_new, 0)), l_new+1+p), 0)
                    else:
                        return ((C[0], 0), 1)
            else:
                (A, m) = x[0]
                if m == 1:
                    return (((A, ((), 1)), q+1), 0)
                else:
                    ((A_new, Bp_new), l_new) = ChuVandermond(n+q+1,n,n-p-q-3)((A, 1))[0]
                    B_new = complement(2*n-l_new-p-3)((Bp_new,0))[0]
                    return (((A_new, (B_new, 0)), l_new+1+p), 0)
        return psi
    def rho5b(p, q):
        if p == q == n - 2:
            return (lambda x: ((((), 1),1) if x[1] == 0 else (((((), 1), ()), n-1),0)))
        def psi(x):
            if x[1] == 0:
                (((A, m), B), l) = x[0]
                if m == 1:
                    return ((B, 1), 1)
                else:
                    Ap = complement(p+(l-1)+2)((A,0))[0]
                    C = ChuVandermond(p+3,n,q)((((B,Ap),q-(l-1)),0))
                    if C[1] == 0:
                        ((B_new, Ap_new), l_new) = C[0]
                        A_new = complement(p+(q-l_new)+2)((Ap_new,0))[0]
                        return ((((A_new, 0), B_new), q-l_new+1), 0)
                    else:
                        return ((complement(n-p-3)((C[0],0))[0], 0), 1)
            else:
                (Ap, m) = x[0]
                if m == 1:
                    return (((((), 1), Ap), p+1), 0)
                else:
                    A = complement(n-p-3)((Ap, 0))[0]
                    ((B_new, Ap_new), l_new) = ChuVandermond(p+3,n,q)((A, 1))[0]
                    A_new = complement(p+(q-l_new)+2)((Ap_new,0))[0]
                    return ((((A_new, 0), B_new), q-l_new+1), 0)
        return psi
    def rho5c(p, q):
        if q != k - 2:
            return sijectionidentity
        else:
            def psi(x):
                if x[1] == 0:
                    ((A, Bp), lp) = x[0]
                    B = complement(2*n - (lp-1) - 3)((Bp,0))[0]
                    l = lp - p - 1
                    C = ChuVandermond(n, n, n - p - 2)((((A, B), l), 0))
                    if C[1] == 1:
                        return ((), 1)
                    else:
                        ((A_new, B_new), lp_new) = C[0]
                        l_new = lp_new + p + 1
                        Bp_new = complement(2*n - (l_new-1) - 3)((B_new,0))[0]
                        return (((A_new, Bp_new), l_new), 0)
                else:
                    return ((((), ()), n-1), 0)
            return psi
    def rho5d(p, q):
        if p != n - 2:
            return sijectionidentity
        else:
            def psi(x):
                if x[1] == 0:
                    ((Bp, A), lp) = x[0]
                    Bp2 = tuple([i-(k-1) for i in Bp[k-2:]])
                    B = complement(n + (lp-1) + 1 - k)((Bp2,0))[0]
                    l = q - (lp-1)
                    C = ChuVandermond(n, n, q + 2 - k)((((A, B), l), 0))
                    if C[1] == 1:
                        return ((), 1)
                    else:
                        ((A_new, B_new), lp_new) = C[0]
                        l_new = q - lp_new + 1
                        Bp2_new = complement(n + (l_new-1) + 1 - k)((B_new,0))[0]
                        Bp_new = tuple(list(range(1,k-1)) + [i + k-1 for i in Bp2_new])
                        return (((Bp_new, A_new), l_new), 0)
                else:
                    return (((tuple(range(1,k-1)), ()), k-1), 0)
            return psi
    def rho5i(p, q):
        return sijectioncompose([rho5a(p, q), sijectioninverse(rho5b(p, q))])
    def rho5ii(p, q):
        return sijectioncompose([rho5c(p, q), sijectioninverse(rho5d(p, q))])
    tau5 = sijectiondisjointunion2(
            sijdisun(lambda pi: sijectioncartesian([sijectiondisjointunion2(
                rho5i(p, pi[p]-1), rho5ii(p, pi[p]-1)) for p in range(n-1)])),
            sijdisun(lambda pi: sijectioncartesian([rho5i(p, pi[p]-1) for p in range(n-1)])))
    def psi6(x):
        if x[1] == 0:
            (((A, B), k), p) = x[0]
            return ((((A, p), B), k), 1)
        else:
            (((A, p), B), k) = x[0]
            return ((((A, B), k), p), 0)
    tau6 = sijectiondisjointunion2(sijdisun(lambda pi: sijectioncartesian([psi6]*(n-1))), sijectionidentity)
    tau7 = sijectiondisjointunion2(detproduct(n - 1), detproduct(n - 1))
    def tau8(x):
        w = (tuple([()]*(n-1)), tuple(range(1, n)))
        if x[1] == 0:
            (((A, pi), y), q) = x[0]
            return (((A, pi), q), 1)
        else:
            ((A, pi), q) = x[0]
            return ((((A, pi), w), q), 0)
    def tau9(x):
        if x[1] == 0:
            ((A, pi), q) = x[0]
            if q == 1:
                return (((tuple(list([(A[i], 0) for i in range(len(A))])), pi), 0), 0)
            else:
                if A[-1][1] == 0:
                    return (((tuple([A[i][0] for i in range(len(A))]), pi), 1), 0)
                else:
                    return ((tuple([A[i][0] for i in range(len(A))]), pi), 1)      
        else:
            (A, pi) = x[0]
            return (((tuple(list([(A[i], 0) for i in range(n-2)]) + [(A[-1], 1)]
                            ), pi), 0), 0)
    def tau10(x):
        if x[1] == 0:
            (u, pi) = x[0]
            T = tuple(filter(lambda i: pi[i - 1] == i and u[i - 1][1] == 1, range(1, n - 1)))
            U = complement(n - 1)((T, 0))[0]
            sigma = [pi[i - 1] for i in U]
            pi_new = tuple([U.index(pi[i - 1]) + 1 for i in U])
            u_new = tuple([u[i - 1][0] if i < n - 1 else u[i - 1] for i in U])
            return (((u_new, pi_new), U), 1)
        else:
            ((u, pi), U) = x[0]
            sigma = [U[pi[i] - 1] for i in range(len(U))]
            pi_new = list(range(1, n))
            u_new = [((), 1)]*(n - 1)
            j = 0
            for i in range(n - 1):
                if i + 1 in U:
                    pi_new[i] = sigma[j]
                    u_new[i] = (u[j], 0) if i < n - 2 else u[j]
                    j += 1
            return ((tuple(u_new), tuple(pi_new)), 0)
    def tau11(x): # Gessel-Viennot
        if x[1] == 0:
            ((U, pi), T) = x[0]
            m = len(T)
            points = find_points(T, (U, pi))
            intersections = list(filter(lambda ij: not(set(points[ij[0]]).isdisjoint(set(points[ij[1]]))),
                         [(i, j) for i in range(m - 1) for j in range(i + 1, m)]))
            if intersections == []:
                return (x[0], 1)
            else:
                i = intersections[0][0]
                p = 0
                while all([points[i][p] not in points[q] for q in range(i + 1, m)]):
                    p += 1
                j = i + 1
                while points[i][p] not in points[j]:
                    j += 1
                q = points[j].index(points[i][p])
                pointsi = points[i]
                points[i] = points[i][:p] + points[j][q:]
                points[j] = points[j][:q] + pointsi[p:]
                Ui = tuple(filter(lambda p: points[i][p][0] > points[i][p - 1][0],
                                  range(1, len(points[i]))))
                Uj = tuple(filter(lambda p: points[j][p][0] > points[j][p - 1][0],
                                  range(1, len(points[j]))))
                U_new = tuple(list(U[:i]) + [Ui] + list(U[i + 1: j]) + [Uj] + list(U[j + 1:]))
                pi_new = tuple(list(pi[:i]) + [pi[j]] + list(pi[i + 1: j]) + [pi[i]] + list(pi[j + 1:]))
                return (((U_new, pi_new), T), 0)
        else:
            return (x[0], 0)
    tau12 = toDPP
    return sijectioncompose([tau1, tau2, tau3, tau4, tau5, tau6, tau7, tau8, tau9, tau10, tau11, tau12])

## phij(n, j, par) are the auxiliary sijections needed for Problem 2.
def phij(n, j, par):
    def tau(x):
        if x[1] == 0:
            ((B, A), p) = x[0]
            C = Aisijectionprime(n, j, par)((((B, A), p + 1), 0))[0]
            if C[1] == 1:
                return ((C[0][1], C[0][0][0]), 1)
            else:
                ((B_new, A_new), p_new) = C
                return (((B_new, A_new), p_new - 1), 0)
        else:
            (A, B) = x[0]
            C = Aisijectionprime(n, j, par)(((((B, 0), A), 1), 0))[0]
            ((B_new, A_new), p_new) = C
            return (((B_new, A_new), p_new - 1), 0)
    return tau

## DPPASM(n, j, par) is the sijection from Problem 2.
def DPPASM(n, j, par):
    tau1 = sijectioncartesian([sijectioninverse(fromdet(n)), sijectionidentity])
    tau2 = Cramer(tuple([phij(n, i, par) for i in range(2, n + 1)]), j-1)
    def tau3(x):
        if x[1] == 0:
            (B, pi) = x[0]
            i = pi.index(j-1) + 1
            return ((B[i-1][0], (tuple(list(B[:i-1]) + [B[i-1][1]] + list(B[i:])), pi)), 1)
        else:
            (A, (B, pi)) = x[0]
            i = pi.index(j-1) + 1
            return ((tuple(list(B[:i-1]) + [(A, B[i-1])] + list(B[i:])), pi), 0)
    tau4 = sijectioncartesian([sijectionidentity, fromdet2(n, j)])
    return sijectioncompose([tau1, tau2, tau3, tau4])


### checking trinomial
##a = 4
##b = 8
##c = 3
##S = cartesian([ksubsets(a+b+c,a),ksubsets(b+c,b)])
##T = cartesian([ksubsets(a+b+c,b),ksubsets(a+c,c)])
##print("S: ",len(S))
##print("T: ",len(T))
##print(bijectionQ(S,trinomial(a,b,c),T))

# checking MTtoASM
##n = 5
##S = montriang(tuple(range(1,n+1)))
##T = A(n)
##phi = MTtoASM
##print(bijectionQ(S, phi, T))

# checking subsetstocompositions 
##n = 8
##k = 3
##S = ksubsets(n,k)
##T = compositions(n-k,k+1)
##print("S: ",len(S))
##print("T: ",len(T))
##print(bijectionQ(S,subsetstocompositions(n,k),T))

#checking ChuVandermond
##a = 5
##b = 12
##c = 4
##S = ssdisjointunion(ssinterval(0,c),lambda j:
##                    sspm(j)((cartesian([ksubsets(b,j),ksubsets(a+c-j-1,a-1)]),[])))
##S1 = ssdisjointunion(ssinterval(0,c),lambda j:
##                    sspm(j)((cartesian([ksubsets(b,j),compositions(c-j,a)]),[])))
##
##if a >= b:
##    T = (ksubsets(a+c-b-1,c),[])
##else:
##    T = sspm(c)((ksubsets(b-a,c),[]))
##print(sssize(T))
##print("S: ",len(S[0])," ",len(S[1]))
##print("S1: ",len(S1[0])," ",len(S1[1]))
##print("T: ",len(T[0])," ",len(T[1]))
##phi = ChuVandermond(a,b,c)
##print(sijectionQ(S, phi, T))

# checking Bisijection
##n = 4
##for i in range(1,n+1):
##    S = ssdisjointunion(ssinterval(1,n),lambda j: sspm(j+1)(sscartesian([
##        (ksubsets(2*n-i-1,n-i-j+1),[]), (Bi(n,j),[])])))
##    T = (Bi(n,i),[])
##    print("S: ",len(S[0])," ",len(S[1]))
##    print("T: ",len(T[0])," ",len(T[1]))
##    phi = Bisijection(n,i)
##    print(sijectionQ(S, phi, T))

# checking Bisijectionprime
##n = 3
##for i in range(1,n+1):
##    S = ssdisjointunion(ssinterval(1,n),lambda j: sscartesian([
##        ssdisjointunion2(sspm(j+1)((ksubsets(2*n-i-1,n-i-j+1),[])),
##                         ([],[()]) if i == j else ssempty()),(Bi(n,j),[])]))
##    print("S: ",len(S[0])," ",len(S[1]))
##    phi = Bisijectionprime(n,i)
##    print(sijectionQ(S, phi, ssempty()))

### checking detproduct
##m = 3
##P = ((ssinterval(1,5),ssinterval(-3,4),ssinterval(4,0)),
##     (ssinterval(4,1,),ssinterval(0,5),ssinterval(2,2)),
##     (ssinterval(3,2),ssinterval(3,-2),ssinterval(4,6)))
##Q = ((ssinterval(2,4),ssinterval(1,3),ssinterval(3,1)),
##     (ssinterval(5,5),ssinterval(4,-2),ssinterval(4,5)),
##     (ssinterval(1,3),ssinterval(0,5),ssinterval(2,0)))
##R = matrixproduct(P, Q, m, m, m)
##S = det(R)
##T = sscartesian([det(P),det(Q)])
##start = time.time()
##print("S: ",len(S[0])," ",len(S[1]))
##print("T: ",len(T[0])," ",len(T[1]))
##phi = detproduct(m)
##print(sijectionQ(S, phi, T))
##print(time.time() - start)

# checking Cramer
##m = 3
##P = ((ssinterval(1,5),ssinterval(-3,4),ssinterval(3,0)),
##    (ssinterval(1,3),ssinterval(0,5),ssinterval(2,1)),
##     (ssinterval(1,1),ssinterval(-5,-2),ssinterval(0,1)))
##X = (ssinterval(4,1), ssinterval(3,3),ssinterval(-3,-5))
##PX = tuple([ssdisjointunion(ssinterval(1,m), lambda j:
##            sscartesian([P[i][j-1], X[j-1]])) for i in range(m)])
##j = 3
##S = sscartesian([det(P), X[j-1]])
##pphi = tuple([sijectiontoempty(PX[i]) for i in range(m)])
##Q = [[ssdisjointunion(ssinterval(1,m), lambda l: sscartesian([P[p][l-1],X[l-1]]))
##      if q+1 == j else P[p][q] for q in range(m)] for p in range(m)]
##W = [[ssdisjointunion(ssinterval(1,m), lambda l: ssempty())
##      if q+1 == j else P[p][q] for q in range(m)] for p in range(m)]
##T = det(W)
##phi = Cramer(pphi, j)
##print(sijectionQ(S,phi,T))

# checking solveequation
##m = 3
##P = ((ssinterval(1,5),ssinterval(-3,4),ssinterval(3,0)),
##    (ssinterval(1,3),ssinterval(0,5),ssinterval(2,1)),
##     (ssinterval(1,1),ssinterval(-5,-2),ssinterval(0,1)))
##X = (ssinterval(4,1), ssinterval(3,3),ssinterval(-3,-5))
##PX = tuple([ssdisjointunion(ssinterval(1,m), lambda j:
##            sscartesian([P[i][j-1], X[j-1]])) for i in range(m)])
##pphi = tuple([sijectiontoempty(PX[i]) for i in range(m)])
##S = tuple([sscartesian([det(P),X[i]]) for i in range(m)])
##print([sijectionQ(S[i-1],solveequation(pphi, i),ssempty()) for i in range(1,m+1)])

# checking elementary1
##kk = (1,2,3,5)
##n = len(kk)
##j = 2
##start = time.time()
##S = Ej(kk,j)
###T = ssdisjointunion(sscartesian([ssinterval(kk[i],kk[i+1]) for i in range(n-1)]), lambda ll: Ej(ll,j))
##print("S",len(S[0]),len(S[1]))
###print("T",len(T[0]),len(T[1]))
##print(time.time() - start)
###phi_aux = elementary_aux(kk, j)
###start = time.time()
###print(sijectionQ(S,phi_aux,T))
###print(time.time() - start)
##start = time.time()
##phi = elementary1(kk, j)
##print(sijectionQ(S,phi,ssempty()))
###s = S[0][0]
###print(s)
###print(phi((s,0)))
##print(time.time() - start)

# checking elementary2
##kk = (1,5,2,4)
##n = len(kk)
##j = 3
##start = time.time()
##S = Fj(kk,j)
##print("S",len(S[0]),len(S[1]))
##print(time.time() - start)
##start = time.time()
##phi = elementary2(kk, j)
##print(sijectionQ(S,phi,ssempty()))
##print(time.time() - start)

# checking elementary1prime
##kk = (1,4,-2,4)
##kkp = tuple([kk[0]+1] + list(kk[1:]))
##j = 2
##n = len(kk)
##
##S = Ejprime(kk, j)
####T = ssdisjointunion2(Ejprime(kkp,j-1),ssminus(Ejprime(kk,j-1)))
####V = ssdisjointunion2(ssdisjointunion(ssinterval(0,j-1), lambda i: sspm(j-1-i)(
####        sscartesian([(ksubsets(j-1,i),[]),GT(tuple([kk[0] + i+1] + list(kkp[1:])))]))),
####                     ssminus(ssdisjointunion(ssinterval(0,j-1), lambda i: sspm(j-1-i)(
####        sscartesian([(ksubsets(j-1,i),[]),GT(tuple([kk[0] + i] + list(kk[1:])))])))))
##T = ssdisjointunion(ssinterval(0,j), lambda i: sspm(j-i)(
##        sscartesian([(ksubsets(j,i),[]),GT(tuple([kk[0] + i] + list(kk[1:])))])))
##print("S: ",len(S[0])," ",len(S[1]))
####print("U: ",len(U[0])," ",len(U[1]))
####print("V: ",len(V[0])," ",len(V[1]))
##print("T: ",len(T[0])," ",len(T[1]))
##phi = elementary1prime(kk, j)
####s = S[0][0]
####print(s)
####print(phi((s,0)))
##start = time.time()
##print(sijectionQ(S,phi,T))
##print(time.time() - start)

### checking elementary2prime
##kk = (1,4,-2,0)
##kkp = tuple([kk[0]-1] + list(kk[1:]))
##j = 2
##
##n = len(kk)
##S = Fjprime(kk, j)
####T = ssdisjointunion2(Ejprime(kkp,j-1),ssminus(Ejprime(kk,j-1)))
####V = ssdisjointunion2(ssdisjointunion(ssinterval(0,j-1), lambda i: sspm(j-1-i)(
####        sscartesian([(ksubsets(j-1,i),[]),GT(tuple([kk[0] + i+1] + list(kkp[1:])))]))),
####                     ssminus(ssdisjointunion(ssinterval(0,j-1), lambda i: sspm(j-1-i)(
####        sscartesian([(ksubsets(j-1,i),[]),GT(tuple([kk[0] + i] + list(kk[1:])))])))))
##T = ssdisjointunion(ssinterval(0,j), lambda i: sspm(j-i)(
##        sscartesian([(ksubsets(j,i),[]),GT(tuple([kk[0] - i] + list(kk[1:])))])))
##print("S: ",len(S[0])," ",len(S[1]))
####print("U: ",len(U[0])," ",len(U[1]))
####print("V: ",len(V[0])," ",len(V[1]))
##print("T: ",len(T[0])," ",len(T[1]))
###phi = elementary2prime_aux(kk, j)
##phi = elementary2prime(kk, j)
##start = time.time()
##print(sijectionQ(S,phi,T))
##print(time.time() - start)

# checking lefttoright
##kk = (1,-3,2,2)
##n = len(kk)
##Tp = AP(n-1)[0][0]
##start = time.time()
##S = ssdisjointunion(AR(n-1), lambda mu:
##                    GT(tuple([kk[i] + c(addleft(Tp,mu,n),n,i+1) for i in range(n)])))
##T = ssdisjointunion(AR(n-1), lambda mu:
##                    GT(tuple([kk[0] + c(addright(Tp,mu,n),n,n)]
##                             + [kk[i] + c(addright(Tp,mu,n),n,i) for i in range(1,n)])))
##
##print("S: ",len(S[0])," ",len(S[1]))
##print("T: ",len(T[0])," ",len(T[1]))
##phi = lefttoright(kk,Tp)
##print(time.time() - start)
##start = time.time()
##print(sijectionQ(S,phi,T))
##print(time.time() - start)

### checking rotation
##kk = (1,2,3,4,5)
##n = len(kk)
##start = time.time()
##S = MT(kk)
##T = sspm(n-1)(MT(rot(kk)))
##print("S: ",len(S[0])," ",len(S[1]))
##print("T: ",len(T[0])," ",len(T[1]))
##print(time.time() - start)
##phi = rotation(kk,0)
##start = time.time()
##print(sijectionQ(S,phi,T))
##print(time.time() - start)

#checking fromMTsubi
##kk = (1,3,4,6,8)
##n = len(kk)
##i = 3
##S = MTsubi(kk,i)
###S1 = ssdisjointunion((list(filter(lambda l: all(l[j] < l[j+1] for j in range(len(l)-1)),
###        sscartesian([ssinterval(kk[j+1],kk[j+2]) for j in range(n-2)])[0])),[]),
###            lambda l: MTsubi(tuple([kk[0]] + list(l)),i-1))
###S2 = ssdisjointunion((list(filter(lambda l: all(l[j] < l[j+1] for j in range(len(l)-1)),
###        sscartesian([ssinterval(kk[j+1],kk[j+2]) for j in range(n-2)])[0])),[]),
###            lambda l: ssdisjointunion(ssinterval(0,i-2), lambda j: sspm(j)(sscartesian(
###        [(ksubsets(i-2,j),[]), MT(tuple([kk[0]+j+1] + list(l)))]))))
##T = ssdisjointunion(ssinterval(0,i-1), lambda j: sspm(j)(sscartesian(
##        [(ksubsets(i-1,j),[]), MT(tuple([kk[0]+j+1] + list(kk[1:])))])))
##print("S: ",len(S[0])," ",len(S[1]))
###print("S1: ",len(S1[0])," ",len(S1[1]))
###print("S2: ",len(S2[0])," ",len(S2[1]))
##print("T: ",len(T[0])," ",len(T[1]))
##phi = fromMTsubi(kk,i)
##print(sijectionQ(S,phi,T))

#checking fromMTsupi
##kk = (1,3,4,6,8)
###kk = (3,)
##n = len(kk)
##i = 3
##S = MTsupi(kk,i)
###S1 = ssdisjointunion((list(filter(lambda l: all(l[j] < l[j+1] for j in range(len(l)-1)),
###        sscartesian([ssinterval(kk[j],kk[j+1]) for j in range(n-2)])[0])),[]),
###            lambda l: MTsupi(tuple(list(l)+[kk[-1]]),i-1))
###S2 = ssdisjointunion((list(filter(lambda l: all(l[j] < l[j+1] for j in range(len(l)-1)),
###        sscartesian([ssinterval(kk[j],kk[j+1]) for j in range(n-2)])[0])),[]),
###            lambda l: ssdisjointunion(ssinterval(0,i-2), lambda j: sspm(j)(sscartesian(
###        [(ksubsets(i-2,j),[]), MT(tuple(list(l)+[kk[-1]-j-1]))]))))
##T = ssdisjointunion(ssinterval(0,i-1), lambda j: sspm(j)(sscartesian(
##        [(ksubsets(i-1,j),[]), MT(tuple(list(kk[:-1]) + [kk[-1]-j-1]))])))
##print("S: ",len(S[0])," ",len(S[1]))
###print("S1: ",len(S1[0])," ",len(S1[1]))
###print("S2: ",len(S2[0])," ",len(S2[1]))
##print("T: ",len(T[0])," ",len(T[1]))
##phi = fromMTsupi(kk,i)
##print(sijectionQ(S,phi,T))

#checking Aisijection       
##n = 4
##i = 2
##S = ssdisjointunion(ssinterval(1,n),lambda j: sspm(j+1)(sscartesian([
##    (ksubsets(2*n-i-1,n-i-j+1),[]), (Ai(n,j),[])])))
####S1 = ssdisjointunion(ssinterval(i,2*n-1),lambda j: sspm(n-j)(sscartesian([
####   (ksubsets(2*n-i-1,j-i),[]), (Ai(n,j),[])])))
####S4 = ssdisjointunion(ssinterval(0,2*n-i-1),lambda j: sspm(n-j-1)(sscartesian([
####    (ksubsets(2*n-i-1,j),[]), MTsubi(tuple(range(1,n+1)),2*n-j-1)])))
####S5 = ssdisjointunion(ssinterval(0,2*n-i-1),lambda j: sspm(n-j-1)(sscartesian([
####    (ksubsets(2*n-i-1,j),[]), ssdisjointunion(ssinterval(0,2*n-j-2), lambda p:
####        sspm(p)(sscartesian([(ksubsets(2*n-j-2,p),[]), MT(tuple([2+p] + list(range(2,n+1))))])))])))
####S6 = ssdisjointunion(ssinterval(0,2*n-2),lambda p: sspm(n+p-1)(sscartesian([
####    ssdisjointunion(ssinterval(0,2*n-p-2), lambda j:
####        sspm(j)(sscartesian([(ksubsets(2*n-i-1,j),[]),
####                (ksubsets(2*n-j-2,p),[])]))), MT(tuple([2+p] + list(range(2,n+1))))])))
####S7 = ssdisjointunion(ssinterval(0,2*n-2),lambda p: sspm(n+p-1)(sscartesian([
####    (ksubsets(i-1,2*n-p-2), []), MT(tuple([2+p] + list(range(2,n+1))))])))
####S8 = ssdisjointunion(ssinterval(0,i-1),lambda p: sspm(n+p-1)(sscartesian([
####    (ksubsets(i-1,p), []), MT(tuple([2*n-p] + list(range(2,n+1))))])))
####S9 = ssdisjointunion(ssinterval(0,i-1),lambda p: sspm(p)(sscartesian([
####    (ksubsets(i-1,p), []), MT(tuple(list(range(2,n+1)) + [n-p]))])))
####S10 = ssdisjointunion(ssinterval(0,i-1),lambda p: sspm(p)(sscartesian([
####    (ksubsets(i-1,p), []), MT(tuple(list(range(1,n)) + [n-1-p]))])))
####S11 = MTsupi(tuple(range(1,n+1)),i)
####S12 = (list(filter(lambda T:T[i-1][-1] == 1, A(n))),[])
##T = (Ai(n,i),[])
##print("S: ",len(S[0])," ",len(S[1]))
####print("S1: ",len(S1[0])," ",len(S1[1]))
####print("S4: ",len(S4[0])," ",len(S4[1]))
####print("S5: ",len(S5[0])," ",len(S5[1]))
####print("S6: ",len(S6[0])," ",len(S6[1]))
####print("S7: ",len(S7[0])," ",len(S7[1]))
####print("S8: ",len(S8[0])," ",len(S8[1]))
####print("S9: ",len(S9[0])," ",len(S9[1]))
####print("S10: ",len(S10[0])," ",len(S10[1]))
####print("S11: ",len(S11[0])," ",len(S11[1]))
##print("T: ",len(T[0])," ",len(T[1]))
##phi = Aisijection(n,i,0)
##start = time.time()
##print(sijectionQ(S, phi, T))
##print(s,phi((s,1)))
##print(time.time() - start)

# checking Aisijectionprime
##n = 3
##par = 0
##for i in range(1,n+1):
##    S = ssdisjointunion(ssinterval(1,n),lambda j: sscartesian([
##        ssdisjointunion2(sspm(j+1)((ksubsets(2*n-i-1,n-i-j+1),[])),
##                         ([],[()]) if i == j else ssempty()),(Ai(n,j),[])]))
##    print("S: ",len(S[0])," ",len(S[1]))
##    start = time.time()
##    phi = Aisijectionprime(n,i,par)
##    print(sijectionQ(S, phi, ssempty()))
##    print(time.time() - start)

# checking AiBiequation
##n = 4
##m = n-1
##X = [ssdisjointunion2(sscartesian([(Bi(n, 1), ()), (Ai(n, j),())]),
##                      ssminus(sscartesian([(Ai(n, 1), ()), (Bi(n, j),())])))
##     for j in range(2,n+1)]
##P = [[ssdisjointunion2(sspm((q+2)+1)((ksubsets(2*n-(p+2)-1,n-(p+2)-(q+2)+1),[])),
##        ([],[()]) if p == q else ssempty()) for q in range(n-1)] for p in range(n-1)]
##PX = tuple([ssdisjointunion(ssinterval(1,m), lambda q:
##            sscartesian([P[p][q-1], X[q-1]])) for p in range(m)])
##
##print([(len(PX[p][0]),len(PX[p][1])) for p in range(m)])
##
##X0 = ssdisjointunion2(sscartesian([(Bi(n, 1), ()), (Ai(n, 1),())]),
##                      ssminus(sscartesian([(Ai(n, 1), ()), (Bi(n, 1),())])))
##P0 = [ssdisjointunion2((ksubsets(2*n-(p+2)-1,n-(p+2)-1+1),[]),
##        ssempty()) for p in range(n-1)]
##for i in range(2,n+1):
##    phi = AiBiequation(n,i,0)
##    start = time.time()
##    print(sijectionQ(PX[i-2],phi,ssempty()))
##    print(time.time() - start)

# checking fromdet
##n = 3
##start = time.time()
##P = [[ssdisjointunion2(sspm((q+2)+1)((ksubsets(2*n-(p+2)-1,n-(p+2)-(q+2)+1),[])),
##        ([],[()]) if p == q else ssempty()) for q in range(n-1)] for p in range(n-1)]
##Pp = [[ssdisjointunion2(sspm((q+2)+1)((ksubsets(2*n-(p+2)-1,n-(p+2)-(q+2)+1),[])),
##        ([],[()]) if p == q else ssempty()) for q in range(n-2)] for p in range(n-2)]
##S = [[sspm(p+q)((ksubsets(n,q-p),[])) for q in range(n-2)] for p in range(n-2)]
##print("det(S) = ",det(S))
##Q = [[ssdisjointunion2((ksubsets(p+q+2,q),[]),
##        ([()],[]) if p == q else ssempty()) for q in range(n-2)] for p in range(n-2)]
##R = det(P)
##W1 = sspm(n-1)(ssdisjointunion((subsets(list(range(1,n-1))), []), lambda T:
##    nonintersecting(T, det([[(ksubsets(T[p]+T[q],T[q]-1),[]) for q in range(len(T))]
##                         for p in range(len(T))]))))
##print(W1)
##W = sspm(n-1)((DPP(n-1),[]))
##print("R",len(R[0]),len(R[1]))
##print("W",len(W[0]),len(W[1]))
##print(time.time() - start)
##start = time.time()
##phi = fromdet(n)
##print(sijectionQ(R,phi,W))
##print(time.time() - start)

### checking fromdet2
##n = 5
##k = 3
##B = [[(ssdisjointunion2(sspm((q+2))((ksubsets(2*n-(p+2)-1,n-(p+2)-(q+2)+1),[])),
##        ([()],[]) if p == q else ssempty())) for q in range(n-1)] for p in range(n-1)]
##C = [[ssempty() if q + 2 != k else (ksubsets(2*n-(p+2)-1,n-(p+2)),[]) for q in range(n-1)] for p in range(n-1)]
##Q = [[(ssdisjointunion2((ksubsets((p+1)+(q+1),q),[]) if p != n-2 else ssempty(),
##        ([()],[]) if p == q else ssempty())) for q in range(n-1)] for p in range(n-1)]
##R = [[([tuple(list(range(1,k-1)) + [i + k-1 for i in R]) for R in
##        ksubsets(n+(q+1)-k,(q+1)-k+1)], []) if p == n-2 else ssempty()
##        for q in range(n-1)] for p in range(n-1)]
##P = [[B[p][q] if q + 2 != k else C[p][q]
##              for q in range(n-1)] for p in range(n-1)]
##T = [[Q[p][q] if p + 2 != n else R[p][q]
##              for q in range(n-1)] for p in range(n-1)]
##U = det(P)
##V = (DPPi(n, k), [])
##print("U: ",len(U[0])," ",len(U[1])," ", sssize(U))
##print("V: ",len(V[0])," ",len(V[1])," ", sssize(V))
##phi = fromdet2(n, k)
##print(sijectionQ(U,phi,V))

##M = 10
##start = time.time()
##for j in range(M):
##    phi((random.choice(S),0))
##print((time.time() - start)/M)
##alltimes = []
##for s in S[:10]:
##    start = time.time()
##    phi((s,0))
##    alltimes += [round(time.time() - start, 3)]
##print(alltimes)
##print("S = ", S)
#print("T = ", T)
##QQ = []
##for par in range(-4,6):
##    print(par)
##    phi = MainBijection(n, i, par)
##    QQ += [tuple([T.index(phi((s,0))[0]) for s in S])]
##print(QQ)
#print(S[:7])
#print([(i, T[i]) for i in [34,114,192,33,35]])
#print([(i, T[i]) for i in [114, 152, 191, 33, 31, 30, 230]])

# checking main bijection
##n = 5
##par = 0
##W = ssdisjointunion((subsets(list(range(1,n-1))), []), lambda T:
##    nonintersecting(T, det([[(ksubsets(T[p]+T[q],T[q]-1),[]) for q in range(len(T))]
##                         for p in range(len(T))])))[0]
##W = DPP(n-1)
##print(W)
##for i in range(2, n + 1):
##    print("n = {}, i = {}".format(n, i))
##    start = time.time()
##    S = cartesian([W, Bi(n, 1), Ai(n, i)])
##    T = cartesian([W, Ai(n, 1), Bi(n, i)])
##    print("set sizes: {}, {}".format(len(S), len(T)))
##    phi = MainBijection(n, i, par)
##    print("checking main bijection: {}".format(bijectionQfast(S, phi, T)))
####    for s in S:
####        phi((s,0))
####    for t in T:
####        phi((t,1))
##    print("time needed (in seconds): {}".format(time.time() - start))
##    print("time needed (in minutes): {}".format((time.time() - start)/60))
##    print("time needed (in hours): {}\n".format((time.time() - start)/3600))

# checking DPPASM
##n = 4
##par = 0
##
##for j in range(2, n+1):
##    print("j =",j)
##    S = cartesian([DPPi(n, 1), Ai(n, j)])
##    T = cartesian([Ai(n, 1), DPPi(n, j)])
##    phi = DPPASM(n, j, par)
##    print("set sizes: {}, {}".format(len(S), len(T)))
##    start = time.time()
##    print("checking main bijection: {}".format(bijectionQfast(S, phi, T)))
##    print("time needed (in seconds): {}".format(time.time() - start))
##    print("time needed (in minutes): {}".format((time.time() - start)/60))
##    print("time needed (in hours): {}\n".format((time.time() - start)/3600))