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
    
    
def permutations_all_k(word, k):
    letters = list(word)
    res = [""]

    while len(res[0]) != k:
        next_res = []
        for prefix in res:
            for c in letters:
                next_res.append(prefix + c)
        res = next_res
    return res