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]
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] in
s),int([p[t[a]],p[t]] in s))
print '-'*k

 

[Serge Orlov]

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.

[snip the code]

Can you post a unit test that fails? Otherwise it's not clear what you mean
by saying "mysteriously broken" and "different answer".

Serge.

 

[Jordan Rastrick]

I think I found your bug, although it took a bit of time, a fair bit of
thought, and a fair bit of extra test-framework code - your program is
very concise, reasonably complex, and very unreadable. Its perfect for
testing maths theorems of your own interest, but you probably should
have polished it up a little, and explained a little more precisely
what the actual lines of code were supposed to be doing (as distinct
what mathematical ideas they were testing) before posting it to a forum
with a request for others to debug it.

I sympathise though - I'm a Maths undergraduate student myself, and I
often write dodgy, buggy code like this in high level languages like
Python, Haskell etc to test ideas

Anyway, from what I can tell the problem is with the line

print '%s %5s %3s' %(str([a,b]),int([p[a],p] in
s),int([p[t[a]],p[t]] in s))

I've assumed/deduced you mean for the expression:
([p[a],p] in s)
to test whether (a,b) is an inversion of pt, i.e. is [pt(a),pt(b)] in
the collection s of stepup pairs (thats according to my understanding
of the terms you've used). But s is not complete list of stepup pairs
if you apply the 'xor filter' in the line you've labeled #MYSTERIOUSLY
BROKEN, its the list of stepup pairs sharing a co-ordinate with [a,b].
So you correctly identified the source of the bug as being at that
line.

I think (guess) what youre really trying to do is filter at the
printing stage, so you're just printing at those cases where {a,b} and
{x,y} share one and only one element, and ignoring the other trivial
cases - i'm inferring this from the fact you don't think the 'answers'
should change, just, presumably, the amount of output. This works:

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]
g,h = min(moved), max(moved)
n = len(p) - 1
s = stepups(n)
print '-'*k
print 'p: ' + str(range(n+1)) + '\n ' + str(p)
print '-'*k
print 't = ' + str((g,h))
print '-'*k
print '%s %7s %3s' %('pair','p','pt') + '\n' + '-'*k
for [a,b] in s:
if xor(g in [a,b], h in [a,b]):
print ([p[a],p]), ([p[t[a]],p[t]])
print '%s %5s %3s' %(str([a,b]),int([p[a],p] in
s),int([p[t[a]],p[t]] in s))
print '-'*k

You can replace g and h if you want, they were pretty arbitrary
letters, but whatever you do dont use 'a' and 'b' twice like your
original code did, its awful programming practice. Even in Maths you
wouldnt let one pronumeral stand for two different quantities in the
same proof, its a recipe for disaster.

If this was wrong, and you really did want to test for inversion only
against the reduced set of pairs, a more complete explanation of what
kind of 'wrong answers' you are getting and what kind of 'right
answers' you were expecting might help. As far as I can tell though,
its quite natural the answers will be different when testing against a
subset of the stepup pairs when compared to testing against the whole
set.

Cheers,
Jordan

P.S. Oh, and if you come up with a proof of the proposition, let me
know, I'd like to see it

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]
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] in
s),int([p[t[a]],p[t]] in s))
print '-'*k

 

[Sean McIlroy]

<snip>

Wow. I'd resigned myself to the task of reformulating my question in
an intelligent way, I stopped by just to leave a little note to the
effect that the thread wasn't dead, and I find out the question's been
answered. Thanks very much. I'll let you know how it turns out.

Peace,
Sean

 

[Sean McIlroy]

<later>
Wow again. I had a real "V8 moment" when I looked at your solution
(smacking my forhead, groaning ruefully, etc). You were right: my
intention was simply to hide the trivial cases from view; I completely
missed the fact that I was now testing for membership in a different
set. I should have remembered that python "plays fair", and looked a
little harder to find my mistake.

Thanks again,
Sean

 

[Jordan Rastrick]

<later>
Wow again. I had a real "V8 moment" when I looked at your solution
(smacking my forhead, groaning ruefully, etc). You were right: my
intention was simply to hide the trivial cases from view; I completely
missed the fact that I was now testing for membership in a different
set. I should have remembered that python "plays fair", and looked a
little harder to find my mistake.

Thanks again,
Sean

You're most welcome, I'm glad the solution was the right one.

Its the kind of bug you can stare at mindlessly for hours without
spotting it, but which will often be reasonably transparent to someone
with a fresh perspective on the code.

I had a doozy myself the other night, writing a mergesort for python's
deque class (I can't believe it doesnt come with one!).... the method
would yield a queue with the right elements in it, but in a seemingly
arbitrary order.

Turns out, there was a > sign that needed to be a >= sign. GRRRRRRR.

I bet if I'd posted to this group it would have been spotted in about 3
seconds flat

- Jordan