def perms(w):
    '''pre: w is a string, possibly empty
    post: function returns a list containing all the permutations of w'''
    if w == '':
        return ['']
    elif len(w) == 1:
        return [w]
    else:
        ans = []
        for each in perms(w[1:]):
            for k in range(len(each)+1):
                ans.append(each[:k] +w[0] + each[k:])
        return ans

def main():
    print(perms('cat'))
    x = perms("string")
    print(x, len(x))

main()