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[b]] in
s),int([p[t[a]],p[t[b]]] in s))
I've assumed/deduced you mean for the expression:
([p[a],p[b]] 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]<>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[b]]), ([p[t[a]],p[t[b]]])
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
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 :)
Sean McIlroy wrote:
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
