# Johnson-Trotter Permutaion Algorithm
# Described in Levitin, 2nd ed p 179
# Implemented by Claude Anderson  Oct 5, 2008


left = - 1  # equivalent to the left- and
right = 1   # right-pointing arrows in the book

def swap(list1, list2, i, j):
    "Swap positions i and j in both lists"
    list1[i], list1[j] = list1[j], list1[i]
    list2[i], list2[j] = list2[j], list2[i]
    

class Permutation:
    "Set current to the unpermuted list, and all directions pointing left"
    def __init__(self, n):
        self.current = range(1, n + 1)
        self.direction = [left] * n
        self.n = n
        self.more = True # This is not the last permutation.
                
    def isMobile(self, k):
        ''' An element of a permutation is mobile if its direction "arrow" 
             points to an element with a smaller value.'''
        return k + self.direction[k] in range(self.n) and \
               self.current[k + self.direction[k]] < self.current[k]
    
    def next(self):
        "return current permutation and calculate next one"
        if not self.more:
            return False
        returnValue = [self.current[i] for i in range(self.n)]

        largestMobile = 0
        for i in range(self.n):
            if self.isMobile(i) and self.current[i] > largestMobile:
                    largestMobile = self.current[i]
                    largePos = i     
                       
        if largestMobile == 0: 
            self.more = False  # This is the last permutation
        else:
            swap(self.current, self.direction,
                 largePos, largePos + self.direction[largePos])
            for i in range(self.n):  
                if self.current[i] > largestMobile:  
                    self.direction[i] *= - 1
                    
        return "".join([str(v) for v in returnValue])
        

def main():
    p = Permutation(4)
    list = []
    next = p.next()
    while next:
        list += [next]
        next =  p.next()  
    print list                     
        
main()