Estoy teniendo problemas tratando de hacer un código de permutación con recursión. Se supone que esto devuelve una lista al uso con todas las posiciones posibles para cada letra. así que para la palabracat se supone que volver['cat','act',atc,'cta','tca','tac'] . hasta ahora tengo esto

def permutations(s):
    lst=[]
    if len(s) == 1 or len(s) == 0 :
        # Return a list containing the string, not the string
        return [s]
    # Call permutations to get the permutations that don't include the
    # first character of s
    plst = permutations(s[1:])
    print(plst)
    for item in plst:
        print (item)
        plst= permutations(s[1+1:])

         # Now move through each possible position of the first character
        # and create a new string that puts that character into the strings
        # in plst
        for i in range(len(s)):
            pass
            # Create a new string out of item
            # and put it into lst
        # Modify
    for item in lst:
        print(index)

Hay pasos allí, pero no estoy seguro de cómo usarlos.