Permutation

permutation.py

def memoize(func):
    cache = {}
    def memo(string):
        if not string in cache:
            cache[string] = func(string)
        return cache[string]
    return memo
 
@memoize
def permutations(string):
    if not string:
        return ['']
    results = []
    chars_used = []
    for i, ch in enumerate(string):
        if ch in chars_used:
            continue
        chars_used.append(ch)
        for substr in permutations(string[:i]+string[i+1:]):
            results.append(ch + substr)
    return results