Find the longest word in a symmetric group which satisfies a certain property.

edit

Let $A, B$ be two list of equal length $k$, where $A$ is weakly increasing. For example, $A=[1, 1, 2, 3, 3, 4]$, $B=[12, 9, 10, 15, 15, 14]$.

Define $m_{A,B}$ to be the multiset of pairs $[ A_i, B_i ]$, $i \in k$, (this is a multi-set of pairs of integers, not a list of pairs, so the order of pairs in $m_{A,B}$ does not matter).

By a result in symmetric group, there is a unique element with maximal length (length of the reduced word) in the symmetric group $S_k$ ($k$ is the length of $A$) such that $m_{A,w(sorted(B))} = m_{A,B}$, where $sorted(B)$ is to sorted B such that it is weakly increasing, and the action of $w=s_{i_1} \cdots s_{i_m}$ on a list $L$ is defined by: $s_j(L)$ means exchanging the jth and j+1th elements of $L$, and for $w,w' \in S_k$, $w w'(L) = w(w'(L))$.

There is a method to compute the longest word $w$ by checking all elements in $S_k$. But it takes a long time when $k$ is large. The following function works fine and returns correct result.

 def LongestPerm(A,Bsorted,B):
    k = len(A)
    S = set([(A[i],B[i]) for i in range(k)])
    W = WeylGroup('A'+str(k-1), prefix = 's')

    winner = W.one()
    for w in W:
        wstr = w.inverse().to_permutation_string()
        if set([(A[int(wstr[i])-1],Bsorted[i]) for i in range(k)]) == S:      
            if w.length()>winner.length():
                winner = w
    return winner

In the example that

A=[1, 1, 2, 3, 3, 4]
B=[12, 9, 10, 15, 15, 14]

we have

w=s4*s5*s4*s2*s1

Is there some method to compute $w$ faster (without checking all elements of $S_k$)? Thank you very much.