# Inserting symbol in the string in specified position
def insert_symbol(str, c, pos):
    return str[:pos] + c + str[pos:]

# Generate sequence of strings, obtained as addition of an element to seqence
def insert_everywhere(str, c):
    return map(lambda n: insert_symbol(str, c, n), range(len(str) + 1))

def generatePermutations(s):
    if s == '':
        return []
    # Remove last symbol
    cut = s[:-1]
    last_symbol = s[-1]
    # Get all permutation of cutted string
    cut_permutations = generatePermutations(cut)
    # These permutations will also go to answer
    permutated_list = cut_permutations
    # Get list of all insertions of the symbol to string
    insertions_lists = map(lambda perm: insert_everywhere(perm, last_symbol), permutated_list)
    # Append all possible insertions to target list
    for insertion in insertions_lists:
        permutated_list += insertion
    # Add permutation from standalone last symbol
    permutated_list += [last_symbol]
    return permutated_list