#Generating several classes of pattern avoiding permutations
#according to Steinhaus-Johnson-Trotter order

reset()
n=5    # length of the permutations, changeable
s=[]
for i in range(n+1): s.append(0)  #initial inversion table
L=[]                              #initial list of inversion tables
perm=[]                             
for i in range(n+1): perm.append(0)	#initial permutation
P=[]                              #initial list of permutations

def type_inv_tab():
    t=Sequence(s[1:n+1])
    L.append(t)
    print L.index(t)+1,t

def type_perm():
    perm2=Permutation(perm[0:n])
    perm1=Permutation(perm2).reverse()
    P.append(perm1)
    print P.index(perm1)+1,perm1

def Psi(s,k):
    perm.insert(s,k)

def UndoPsi(s):
    perm.pop(s)

#T1={312,321}
def theta_T1(s,k):
    return 1

#T2={321,3412,4123}
def theta_T2(s,k):
    if s==0:
        u=2
    else:
        u=1
    return u

#T3={312,3421,4321}
def theta_T3(s,k):
    if s==1:
        u=2
    else:u=1
    return u

#T4={p12...(p-1),321,231}
def theta_T4(s,k):
    p=5  # changeable
    if s==0 and k<p-2: u=k+1
    elif s==0 and k==p-2:u=k
    else:u=0
    return u

#Generating procedure, change XX in the function call
#with T1,T2,T3, or T4 to generate the desired list
def GenPAP(k,x,drc,v):
    s[k]=x
    Psi(s[k],k)
    if k==n:
        type_inv_tab()   #choose output: inversion tables, or
        #type_perm()     #permutations  (uncomment the desired output)
    else:
        if k==1:u=1
        else: u=theta_XX(x,v)   
        if drc%2==0:
            for i in [0..u]:
                GenPAP(k+1,i,i,u)
                UndoPsi(s[k+1])
        else:
            for i in reversed[0..u]:
                GenPAP(k+1,i,i+1,u)
                UndoPsi(s[k+1])

#Main call
GenPAP(1,0,0,0)