sorting a list and counting interchanges

[Tim Peters]

[RickMuller]
> I have to sort a list, but in addition to the sorting, I need to
> compute a phase factor that is +1 if there is an even number of
> interchanges in the sort, and -1 if there is an odd number of
> interchanges.

So you want the parity ("sign") of the associated permutation.

> I could write a bubble sort, count the number of interchanges, and
> compute the factor, but I have a feeling that there some
> decorate-sort-undecorate solution buried in this problem somewhere.
> However, I can't see it. Can anyone else help me with this?
>
> I was thinking of something along the lines of zipping the list with a
> range() of the same length, sorting that, and then counting the number
> of times the second list has an item smaller than its previous item. In
> other words
> 
> a = [1,10,2,7]
> b = zip(a,range(len(a)))
> b.sort()
> a_sorted = [i for i,j in b]
> order = [j for i,j in b]

Good so far -- keep that much.  Pass `order` to the function below. 
It computes the sign in linear time.

> phase = 0
> for i in range(len(order)-1):
>    if order[i] > order[i+1]: phase += 1

That part isn't correct.  For example, it computes phase == 1 for both

    [1, 0, 2]
and
    [1, 2, 0]

but those obviously have different parities (since they're one
transposition apart).

> phase = 2*(phase%2)-1
>
> However, I can't prove that this works,

See above for why <wink>.

> and there's *got* to be a more elegant way.

Why?  There's no efficient way to solve this via counting
transpositions directly, although there is an efficient way by
computing the cycle structure.  The following is an elegant way to do
the latter, but "elegance" requires buying into that this is necessary
if you want an efficient solution.

def permsign(p):
    """Return sign of permutation p.

    p must be a permutation of the list range(len(p)).
    The return value is 1 if p is even, or -1 if p is odd.

    >>> for p in ([0,1,2], [0,2,1], [1,0,2],
    ...           [1,2,0], [2,0,1], [2,1,0]):
    ...     print p, permsign(p)
    [0, 1, 2] 1
    [0, 2, 1] -1
    [1, 0, 2] -1
    [1, 2, 0] 1
    [2, 0, 1] 1
    [2, 1, 0] -1
    """

    n = len(p)
    rangen = range(n)
    if sorted(p) != rangen:
        raise ValueError("p of wrong form")

    # Decompose into disjoint cycles.  We only need to
    # count the number of cycles to determine the sign.
    num_cycles = 0
    seen = set()
    for i in rangen:
        if i in seen:
            continue
        num_cycles += 1
        j = i
        while True:
            assert j not in seen
            seen.add(j)
            j = p[j]
            if j == i:
                break

    return (-1)**(n - num_cycles)