from copy import *

def checkSort( L ):
    ''' sort the list by permuting it and checking for sorted
        returns a sorted version of L.  Does not modify L'''
    # keep a list with the current permutation
    currentPermList = range(len(L))
    sortedList = copy(L)
    while not isSorted(sortedList):
        updatePermList(currentPermList)
        for i in range(len(L)):
            sortedList[i] = L[currentPermList[i]]
    return sortedList
    
def isSorted( L ):
    ''' check to see if a list is sorted '''
    if len(L) == 0:
        return True
    for i in range(len(L)-1):
        if L[i+1] < L[i]:
            return False
    return True

def perm( L ):
    ''' a function that generates all permutaions of a list '''
    currentPerm = range(len(L))
    ret = [L]
    while True:
        anotherPerm = updatePermList(currentPerm)
        if not anotherPerm:
            return ret
        nextPerm = []
        for i in range(len(currentPerm)):
            nextPerm += [L[currentPerm[i]]]
        ret += [nextPerm]


def updatePermList( permL ):
    ''' update the index list to get the next permutation of a list '''
    # Starting at the perm index, shuffle the numbers around
    # in a methodical way
    permIndex = len(permL)-2
    c = findNextIndex(permL, permIndex, permL[permIndex]+1)
    while c >= len(permL) and permIndex >= 0:
        permIndex = permIndex - 1
        c = findNextIndex(permL, permIndex, permL[permIndex]+1)
    if permIndex < 0:
        return False  # we finished all the indices
    permL[permIndex] = c
    for j in range(permIndex+1, len(permL)):
        permL[j] = findNextIndex(permL, j, 0)
    return True

def findNextIndex(L, index, startVal):
    '''Find the lowest value that is greater or equal to startVal
        and does not appear in L anywhere to left of index
        not including L[index] '''
    ret = startVal
    okval = False
    while not okval:
        okval = True
        for i in range(index):
            if L[i] == ret:
                ret += 1
                okval = False
                break
    return ret

def permRec( L ):
    ''' recursively generate all of the permutations of L '''
    if len(L) <= 1:
        return [ L ]
    else:
        ret = []
        for i in L:
            Lminusone = copy(L)
            Lminusone.remove(i)
            ret += [[i] + oneperm for oneperm in permRec( Lminusone ) ]
        return ret