the bugs that try men's souls

[Sean McIlroy]

This needs some background so bear with me.

The problem: Suppose p is a permutation on {0...n} and t is the
transposition that switches x and y [x,y in {0...n}]. A "stepup pair"
(just a term I invented) for p is a pair (a,b) of integers in {0...n}
with a<b. A stepup pair (a,b) for p is an "inversion" (standard term)
of p iff (p(a),p(b)) is NOT a stepup pair. Now, if {a,b}={x,y}, then
clearly (a,b) is an inversion of p iff it is NOT an inversion of pt
(functional composition). Also, if {a,b} and {x,y} are disjoint, then
(a,b) is an inversion of p iff it is an inversion of pt. The remaining
cases are the ones where {a,b} and {x,y} have a single element in
common, and of these, there are exactly as many inversions of p as
there are of pt, though in general it is not the same set of stepup
pairs for each function.

The code below represents my attempt to apply python toward getting
insight into why the number of inversions, with exactly one coordinate
in {x,y}, is the same for p and pt. The problem with the code is that
if, at the relevant line ("MYSTERIOUSLY BROKEN"), I use the
commented-out expression instead of the expression that's actually
there, then in some cases the script gives a DIFFERENT ANSWER to the
question whether a given pair is or is not an inversion of p
respectively pt.

I'd sure like to know what's going wrong with this. Here's the code:


## STEPUP PAIR: AN ORDERED PAIR (x,y) OF INTEGERS WITH x<y

stepups = lambda n: n and stepups(n-1) + [[x,n] for x in range(n)] or
[]
xor = lambda x,y: (x and not y) or (y and not x)

def feedback(p,t):
    ## GIVEN A PERMUTATION f AND A STEPUP PAIR s WITH COORDINATES IN
THE RANGE OF f,
    ## SHOW THE INTEGER CASE OF THE PROPOSITION << f(s) IS A STEPUP
PAIR >>
    k = 18
    moved = [i for i in range(len(t)) if t[i]<>i]
    a, b = min(moved), max(moved)
    n = len(p) - 1
    s = stepups(n) ## MYSTERIOUSLY BROKEN: [x for x in stepups(n) if
xor(a in x,b in x)]
    print '-'*k
    print 'p: ' + str(range(n+1)) + '\n   ' + str(p)
    print '-'*k
    print 't = ' + str((a,b))
    print '-'*k
    print '%s %7s %3s' %('pair','p','pt') + '\n' + '-'*k
    for [a,b] in s:
        print '%s %5s %3s' %(str([a,b]),int([p[a],p[b]] in
s),int([p[t[a]],p[t[b]]] in s))
    print '-'*k