Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
60 lines (50 sloc) 1.49 KB
from numpy import abs
import itertools
import operator
import pdb
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 minima(lol):
return list(next(itertools.groupby(sorted(lol, key=f), key=f))[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(p,depth=0):
z=find_breaks(p)
if len(z)==0:
return(0)
smaller=[]
rr=len(z)
small=rr
r=len(p)
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)
elif est<small:
small=est
smaller=[q]
m=[rdistance(u,depth+1)+1 for u in smaller]
return(min(m))
You can’t perform that action at this time.