The code generates all combinations of filename with underscore _:def filename_generator(name, path=''):    names = []    for i in range(len(name)):        p = '_'.join([x for x in name[i:]]) + path        names.append(name[:i] + p)        names += filename_generator(name[:i], p)    return sorted(list(set(names)))for e in filename_generator('longlonglonglonglonglongname'):    print(e)Example:Input: nameOutput: n_a_m_en_a_men_am_en_amena_m_ena_menam_enameMy code works well, but very slowly. How can I optimize the algorithm?
Filename generator with Underscore
python;performance
Note that there are 2n-1 different such names for a string of lengh n, as there can or can not be a _ between any two characters. For your long-long name that makes 134,217,728 variants!Regardless of what algorithm you use, this will take a very long time. One way to work around this, depending on your actual use case, might be to use a generator function. This way, you do not need to calculate all the variants, if maybe you need just a few of them (maybe just enough to find one that does not yet exist?). For example, like this:def filename_generator(name):    if len(name) > 1:        first, rest = name[0], name[1:]        for rest2 in filename_generator(rest):            yield first + rest2            yield first + _ + rest2    else:        yield nameOutput:>>> list(filename_generator(name))['name', 'n_ame', 'na_me', 'n_a_me', 'nam_e', 'n_am_e', 'na_m_e', 'n_a_m_e']Or, building upon the idea by @jacdeh, using binary numbers to determine where to put a _.def filename_generator(name):    d = {0: , 1: _}    for n in range(2**(len(name)-1)):        binary = {:0{}b}.format(n, len(name))        yield''.join(d[s] + c for c, s in zip(name, binary))Or similar, using bit shifting:def filename_generator(name):    for n in range(2**(len(name)-1)):        yield ''.join(c + (_ if n & 1<<i == 1<<i else ) for i, c in enumerate(name))However, either both those implementation are pretty lousy, or it does not help much in the end: They are both about 10 times slower than the recursive function, according to timeit.Here's some timing information, using IPython's %timeit magic method:In [8]: %timeit filename_generator(longname)         # your original function1000 loops, best of 3: 610 s per loopIn [9]: %timeit list(filename_generator1(longname))  # my recursive generator10000 loops, best of 3: 22.5 s per loopIn [10]: %timeit list(filename_generator2(longname)) # my binary generator1000 loops, best of 3: 322 s per loopIn [11]: %timeit partition_string(longname)          # Eric's binary function1000 loops, best of 3: 200 s per loopAnother possibility, as posted in comments, would be to use itertools.product to generate the mask, similar to the binary number solution, but with less involved math.from itertools import product, chaindef filename_generator4(name):    for mask in product((_, ), repeat=len(name) - 1):        yield ''.join(chain(*zip(name, mask + (,))))However, performance is about the same as for the binary solutions. I guess the bottleneck is the number of string concatenations: In the recursive solution, you reuse the partial solutions, while each of the latter solutions construct each solution from scratch, so there are fewer total string concatenation in the recursive case. Not sure, though, so feel free to comment.