Estou tendo problemas para tentar fazer um código de permutação com recursão. Isto é suposto retornar uma lista de volta ao uso com toda a posição posible para cada letra. então para a palavracat é suposto retornar['cat','act',atc,'cta','tca','tac'] . até agora eu tenho esse

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)

Há passos lá, mas não tenho certeza de como usá-los