String Permutations - Tail Recursion - Algorithms to generate all possible permutations of a given string. Why aren't "curried string trees" a thing? I tried my best to stick with tail-recursion, but Python didn't like it.

string_permutations_tail_recursion.py

# This was my idea before starting to code:
#[c, a, t]
    #[a, t]
        #[t, a]
#[(c, [(a, [(t, [])]), (t, [(a, [])])]), (a, [(c, [(t, [])]), (t, [(c, [])])]),...]
#[[cat, cta], [act, atc],...]
#[cat, cta, act, atc]

# Runtime: O(2^n)
# create a list of nested tuples and arrays (char, [tuples]) to represent curried strings
def perms(s: str, i: int = 0, r: list[tuple] = []) -> list[tuple]:
    n = len(s)
    if i == n:
        return r
    else:
        return perms(s, i+1, [*r, (s[i], perms(s[:i]+s[i+1:]))])

# Runtime: O(n)
# curried function, will pre-append the fixed char to the string it's mapped over.
def combine(c: chr):
    # mappee gets mapped!
    def mappee(s: str) -> str:
        return c + s
    return mappee

# Runtime: R <= O(n*m), n = len(list), m = max(map(len, list))
# return a list of the values in nested collections (shallow)
def flatten(lst: list[list[any]]) -> list[any]:
    return [e for l in lst for e in l]

# Runtime: R > O(n!)
# works with longer length strings than the version below
# return a list of the strings represented by a tuple tree.
def extract_strings(t: tuple[str, list[tuple]]) -> list[list[str]]:    
    if not t[1]:
        return [t[0]]
    else:
        return list(map(combine(t[0]), flatten(list(map(extract_strings, t[1])))))

# find permutations, store as a list of nested tuples (curried string trees)
a = perms('taco')
# print(a)
# condense string trees
b = list(map(extract_strings, a))
# output results
c = flatten(b)
print(c, len(c))



# # I think this version is better written, but it does worse in Python.
# # Runtime: R > O(n!)
# # works up to 5 chars, then exceeds max recursion depth
# def extract_strings(lst: list[tuple[str, list[tuple]]], r: list[str] = []) -> list[str]:
#     if not lst:
#         return r
#     else:
#         if not lst[0][1]:
#             return extract_strings(lst[1:], [*r, lst[0][0]])
#         else:
#             return extract_strings([*lst[1:], *list(map(lambda t: (combine(lst[0][0])(t[0]), t[1]), lst[0][1]))], r)
# a = perms('cat')
# b = extract_strings(a)
# print(b, len(b))

# Optimization based on symmetry. (there will always be an even number of permutations, or 1 permutation)
# ['taco', 'taoc', 'tcao', 'tcoa', 'toac', 'toca', 'atco', 'atoc', 'acto', 'acot', 'aotc', 'aoct', 'ctao', 'ctoa', 'cato', 'caot', 'cota', 'coat', 'otac', 'otca', 'oatc', 'oact', 'octa', 'ocat']   24
#    1        7       3      11       9      12       2       8       5      -12     10      -11      4      -10      6      -9      -8      -7      -6      -5      -4      -3      -2      -1      12 + (-, 12)

# expanded, formatted curried-string-tree for "taco"
# [('t',
#     [('a', 
#         [('c', 
#             [('o', [])]), 
#         ('o', 
#             [('c', [])])]),
#     ('c', 
#         [('a', 
#             [('o', [])]),
#         ('o', 
#             [('a', [])])]),
#     ('o',
#         [('a',
#             [('c', [])]),
#         ('c', 
#             [('a', [])])])]),
# ('a', 
#     [('t', 
#         [('c', 
#             [('o', [])]), 
#         ('o', 
#             [('c', [])])]),
#     ('c', 
#         [('t', 
#             [('o', [])]), 
#         ('o', 
#             [('t', [])])]), 
#     ('o', 
#         [('t', 
#             [('c', [])]), 
#         ('c', 
#             [('t', [])])])]), 
# ('c', 
#     [('t', 
#         [('a', 
#             [('o', [])]), 
#         ('o', 
#             [('a', [])])]), 
#     ('a', 
#         [('t', 
#             [('o', [])]), 
#         ('o', 
#             [('t', [])])]), 
#     ('o', 
#         [('t', 
#             [('a', [])]), 
#         ('a', 
#             [('t', [])])])]), 
# ('o', 
#     [('t', 
#         [('a', 
#             [('c', [])]), 
#         ('c', 
#             [('a', [])])]), 
#     ('a', 
#         [('t', 
#             [('c', [])]), 
#         ('c', 
#             [('t', [])])]),
#     ('c', 
#         [('t', 
#             [('a', [])]), 
#         ('a', 
#             [('t', [])])])])]