permutations.py

from collections import deque

def permutations(word):
    if len(word) == 1:
        return [word]

    perms = permutations(word[1:])
    c = word[0]
    res = []

    L = len(perms[0]) + 1
    for perm in perms:
        for i in range(L):
            res.append(perm[:i] + c + perm[i:])
    return res


def permutations_iter(word):
    if len(word) == 1:
        return [word]

    stack = deque(word)
    res = [stack.pop()]

    while stack:
        c = stack.pop()
        next_res = []
        L = len(res[0]) + 1
        for r in res:
            for i in range(L):
                next_res.append(r[:i] + c + r[i:])
        res = next_res
    return res