from sage.combinat.permutation import to_standard

def occurrences(p, pattern):
    """
    Return elements in sequences of distinct blocks order isomorphic
    to `pattern`.
    """
    o = []
    for i, b in enumerate(p):
        q = p[i+1:]
        for e in b:
            o.extend(occurrences_aux(q, [e], pattern))
    return o
            

def occurrences_aux(p, prefix, pattern):
    """
    Return all occurrences of the form `(prefix, suffix)` order
    isomorphic to `pattern`, where `suffix` are elements in sequences
    of distinct blocks of `p`.
    """
    # TODO: we could do better, probably
    if len(pattern) == len(prefix):
        yield prefix
    else:
        pattern_prefix = to_standard(pattern[:len(prefix)+1])
        for i, b in enumerate(p):
            q = p[i+1:]
            for e in b:
                new_prefix = prefix + [e]
                if to_standard(new_prefix) == pattern_prefix:
                    yield from occurrences_aux(q, new_prefix, pattern)

def statistic(p):
    return len(occurrences(p, [1,3,2]))