reversals-sort.py

from numpy import abs
import itertools
import operator

f = operator.itemgetter(1)

def inv_perm(l):
    return([l.index(i)+1 for i in range(1,len(l)+1)])

def prod_perm(p,q):
    return([q[p[i-1]-1] for i in range(1,len(p)+1)])
    
def find_breaks(p):
    breakpoints=[]
    for i,x in enumerate(p):
        if i==0:
            if x!=1:
                breakpoints.append(0)
            continue
        if abs(x-p[i-1])>1:
            breakpoints.append(i)
            continue
    if p[-1]!=len(p):
        breakpoints.append(len(p))
    return(breakpoints)

def rdistance(pl,depth=0):
    smaller=[]
    small=100
    for px in pl:
        (p,state0)=px
        r=len(p)
        z=find_breaks(p)
        if len(z)==0:
            return(depth,state0)
        rr=len(z)
        for t,i in enumerate(z):
            for j in z[t+1:]:
                if j-i>1:
                    q=p[:]
                    q[i:j]=reversed(p[i:j])
                    loss=0
                    if i==0 and q[0]==1: loss=1
                    if i>0 and abs(q[i-1]-q[i])==1: loss+=1
                    if j==r and q[r-1]==len(p): loss+=1
                    if j<r and abs(q[j-1]-q[j])==1: loss+=1
                    est=rr-loss                
                    if est==small:
                        smaller.append((q,state0+[(i,j)]))
                    elif est<small:
                        small=est
                        smaller=[(q,state0+[(i,j)])]
                        
    a=rdistance(smaller,depth+1)
    return(a)

f=open("rosalind_sort.txt","rU")
while True:
    l=f.readline()
    p=map(int,l.split())
    l=f.readline()
    if len(l)==0:
        break
    q=map(int,l.split())
   
    c=prod_perm(p,inv_perm(q))
    #print c
    (depth,flips)=rdistance([(c,[])])
    print depth
    for (u,v) in flips:
        print u+1,v
    print
    l=f.readline()
    if len(l)==0:
        break
f.close()