Filename generator with Underscore

Question

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:

name

Output:

n_a_m_e
n_a_me
n_am_e
n_ame
na_m_e
na_me
nam_e
name

My code works well, but very slowly. How can I optimize the algorithm?

Answer 1

Note that there are 2^n-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 name

Output:

>>> 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 function
1000 loops, best of 3: 610 µs per loop
In [9]: %timeit list(filename_generator1("longname"))  # my recursive generator
10000 loops, best of 3: 22.5 µs per loop
In [10]: %timeit list(filename_generator2("longname")) # my binary generator
1000 loops, best of 3: 322 µs per loop
In [11]: %timeit partition_string("longname")          # Eric's binary function
1000 loops, best of 3: 200 µs per loop

---

Another 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, chain
def 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.

Answer 2

This is a good place to use bitwise operations. Following the suggestion by @jacdeh, for a word such as "dogs" one can make a list of binary strings 000, 001, 010, ..., 111, and put underscores wherever there is a one.

However, you don't actually have to do any conversions, the integers from 0 to 2**len(word-1) ARE the binary strings that you want.

So you can just loop over all these integers, and for each integer, loop over the character positions in the string from 0 to len(word-1), and then check if 2**position has any bits in common with your current binary mask using the bitwise &.

Here is an example implementation:

def partition_string(name, delimiter='_'):
    partitions = []
    for mask in xrange(2**(len(name)-1)):
        part = ''
        for pos in xrange(len(name)-1):
            part = part + name[pos]
            if mask & 2**pos != 0:
                part = part + '_'
        part = part + name[len(name)-1]
        partitions.append(part)
    return partitions

for part in partition_string('dogs'):
    print(part)

Output:

dogs
d_ogs
do_gs
d_o_gs
dog_s
d_og_s
do_g_s
d_o_g_s

Answer 3

The sort in a recursive call is costing you time. This algorithm will be (much) faster:

Count the number of chars in your filename. So nrOfPossiblePositions for a dash equals number of chars - 1. Generate all numbers from 0 - (2 ^ nrOfPossiblePositions) - 1 Convert them to binary and store them in a list. Go through the list, inserting dashes at the position + 1 of the one's in your binary number, working backwards through your filename.

so e.g. 101010 means e_xa_mp_le