Ticket #24659: shifted.sage

"""
sage: P = ShiftedPrimedTableau([[1,2,3,6,7],[4,5]])
sage: Q = ShiftedPrimedTableau([[1,2,3,"4p","6p"],[5,"7p"]])
sage: labels = Q.to_chain() + [mu if is_even(i) else 0 for i, mu in enumerate(P.to_chain()[::-1])][1:]
sage: G = Shifted(shape=[7]*7, labels=labels)
sage: G.to_word()
[5, 6, 7, 2, 4, 1, 3]
"""
def word_to_standard(w):
    """Convert a word with primed entries to a permutation.

    The alphabet is ordered as 
    `X' = \{1' < 1 < 2' < 2 < \cdots < n' < n\}`

    The word is processed beginning with the smallest entry, primed
    entries are standardised from right to left, unprimed from left
    to right.

    EXAMPLES::

        sage: w = ["2'","3'",3,1,"2'","1'",1]
        sage: w = [PrimedEntry(l) for l in w]; w

        sage: word_to_standard(w)
        ([5, 6, 7, 2, 4, 1, 3], [1, 1, 1, 2, 2, 3, 3], [2, 3])

    Sagan, just before Lemma 9.2:

        sage: w = [1, 1, "2p", "1p", "2p", 2, 2, "3p", "1p", "2p"]
        sage: w = [PrimedEntry(l) for l in w]; w
        [1, 1, 2', 1', 2', 2, 2, 3', 1', 2']
        sage: word_to_standard(w)
        ([3, 4, 7, 2, 6, 8, 9, 10, 1, 5], [1, 1, 1, 1, 2, 2, 2, 2, 2, 3], [2, 3])
    """
    n = len(w)
    k = 1
    p = [None]*n # the standardised word
    c = sorted([l.integer() for l in w]) # the content
    s = [] # special entries, leftmost occurrence primed
    A = sorted(set(c)) # letters occurring
    for l in A:
        e = PrimedEntry(l).primed()
        for i in range(len(w)):
            if w[n-i-1] == e:
                leftmost = n-i-1
                p[n-i-1] = k
                k += 1
        e = e.unprimed()
        for i in range(len(w)):
            if w[i] == e:
                if i < leftmost:
                    leftmost = None
                p[i] = k
                k += 1
        if leftmost is not None:
            s.append(l)
    return (p, c, s)