def statistic(S):
    S = sorted( sorted(B) for B in S )
    n = sum( len(B) for B in S )
    ros = 0
    for k in range(len(S)):
        j = S[k][0]
        for l in range(k):
            for i in S[l]:
                if i > j:
                    ros += 1
    return ros

def statistic_alt(pi):
    return len(pattern_occurrences(pi, [[1,3],[2]], [1,2], [], [], []))

def pattern_occurrences(pi, P, First, Last, Arcs, Consecutives):
    """We assume that pi is a SetPartition of {1,2,...,n} and P is a
    SetPartition of {1,2,...,k}.
    """
    occurrences = []
    pi = SetPartition(pi)
    P = SetPartition(P)

    openers = [min(B) for B in pi]
    closers = [max(B) for B in pi]
    pi_sorted = sorted([sorted(b) for b in pi])
    edges = [(a,b) for B in pi_sorted for (a,b) in zip(B, B[1:])]

    for s in Subsets(pi.base_set(), P.size()):
        s = sorted(s)
        pi_r = pi.restriction(s)
        if pi_r.standardization() != P:
            continue

        X = pi_r.base_set()

        if any(X[i-1] not in openers for i in First):
            continue

        if any(X[i-1] not in closers for i in Last):
            continue

        if any((X[i-1], X[j-1]) not in edges for (i,j) in Arcs):
            continue

        if any(abs(X[i-1]-X[j-1]) != 1 for (i,j) in Consecutives):
            continue

        occurrences += [s]
    return occurrences