Creating strings of desired length from a list of substrings

Question

I have a method that generates strings from a list of substrings, and the desired length of all these strings is passed as an argument of the method. Here is my code:

import itertools as it

print make_string(5)

def make_string(wanted_length):
    available_strings = ['AB', 'CDE', 'FGHIJK', 'LMN', 'OP', 'QR', 'ST', 'U']
    minimum_length = 0
    i=2
    while minimum_length < wanted_length:
        products = it.product(*[available_strings]*i)
        str_products = [''.join(map(str,x)) for x in products]
        valid_products = [x for x in str_products if len(x)==wanted_length]
        if valid_products:
            return valid_products
        minimum_length = len(min(str_products, key=len))
        i += 1
    return None

As one can expect, it is incredibly slow and feels overall wrong even if it works. Do you have any input to help me make it better ?

EDIT

As Graipher pointed out in his comment, the above code stops when a valid string of desired length is found but doesn't return all valid strings of desired length. Here is the fixed code, which is obviously even slower than the previous one :)

def make_string(wanted_length):
    all_valid_products = []
    available_strings = ['AB', 'CDE', 'FGHIJK', 'LMN', 'OP', 'QR', 'ST', 'U']
    minimum_length = 0
    i=2
    while minimum_length < wanted_length:
        products = it.product(*[available_strings]*i)
        str_products = [''.join(map(str,x)) for x in products]
        valid_products = [x for x in str_products if len(x)==wanted_length]
        if valid_products:
            all_valid_products.extend(valid_products)
        minimum_length = len(min(str_products, key=len))
        i += 1
    return all_valid_products

Answer 1

The trouble is that you are generating an array with all possible combinations of all possible strings and then whittling it down from there. You end up doing a lot of work you don't have to do. However, it makes for conceptually easy-to-understand code, so I certainly wouldn't call this solution "wrong" (unless it is simply too slow for your actual application). There is often a trade off between "does the job very well" and "easy to understand", and sometimes the latter is the real winner.

In terms of alternate approaches, I just have a general outline of one I can suggest (if it is helpful). Instead of doing this in "string" space you could imagine doing this in "length" space. I.e. instead of thinking of the problem in terms of allowed substrings, think of it in terms of allowed lengths of substrings:

available_strings = ['AB', 'CDE', 'FGHIJK', 'LMN', 'OP', 'QR', 'ST', 'U']

becomes:

strings_by_length = { 1: [ 'U' ], 2: [ 'AB', 'OP', 'QR', 'ST' ], 3: [ 'CDE', 'LMN' ], 6: [ 'FGHIJK' ] }
substring_lengths = strings_by_length.keys()

You now know that you have substrings of length 1, 2, 3, and 6. Then break down the length combinations that are actually applicable. For instance, for a desired length of 5 you can combine substrings of length:

[ 1, 1, 1, 1, 1 ],
[ 1, 1, 1, 2 ],
[ 1, 1, 3 ],
[ 1, 4 ],
[ 1, 2, 2 ],
[ 3, 2 ],
[ 5 ]

You can automatically rule out [1, 4] and [ 5 ] because you have no substrings that match those lengths. You also rule out substring FGHIJK because it is too long for any of your allowed lengths. Of course, generating this list of possibilities is a bit tricky, and then the next part is also tricky:

Take your list of allowed combinations and combine them with the substrings separated by length to get all allowed combinations. I'm not familiar with the itertools library but it might help with that. For instance you could imagine taking combination [ 1, 2, 2 ] and basically doing an iterative combination of:

build_all_combinations( strings_by_length[1], strings_by_length[2], strings_by_length[2] )

Overall, this makes sure you are only calculating combinations for values that you know are allowed, rather than calculating all combinations and then filtering. It has the potential to be more efficient, but the devil is always in the details. Not sure how it will work out in practice, or how easy it will be to write.

Edit to add notes about performance

In case you are new to it, welcome to the world of np-complete problem sets! I think your problem is effectively a variation on the knapsack problem. Reading up on that may give you some ideas of different (and more efficient) approaches to this problem. The short of it is that this can be slow. I'm pretty sure you are running on O(n^2) time, which is not terrible, all things considered. Anyway, onto the steps to optimize:

1. Make your algorithm smarter!

This is basically what I was trying to do. How much my particular algorithm will help will vary depending on the precise problem. If you have a lot of sub strings that are not applicable (i.e. the 'FGHIJK' in your example), then a little intelligence can save you a lot of computation. In the example you gave some the general algorithm I had suggested would have ruled out that one branch before doing any computations, which would have theoretically brought the minimum number of computations down from 8^2 = 64 to 7^2 = 49, a ~25% improvement. However, If all of your substrings had been shorter than the max length, there would have been no improvement.

In practice though I'm comparing to the best-case scenario, and your current algorithm may not be anywhere near that. Your current algorithm may be running in a time substantially slower than the best-case scenario. That is what I meant by "the devil is in the details". Do you know how itertools works? External libraries can make things convenient, but depending on how they run they may actually make your algorithm slower. To really speed things up, it can help to really think through your algorithm and make sure it is running as close to ideal as possible.

2. Run in compiled code

Regardless of how smart your algorithm is, you are still facing at least O(n^2) time. For large n the answer isn't going to be smartness but rather raw computing power. As an interpreted language python is relatively slow, so in cases like this that can be a big source of your problem. This doesn't mean you have to rewrite in C or another language, as python has many built in tools that may delegate parts of your tasks to compiled code. As a general example (which may or may not be helpful for you), in a lot of my computations I used numpy extensively and relied upon its built-in array operations, in particular seeking to avoid for loops. Looping tends to be one of the slowest parts of interpreted languages, while all of numpy's array operations are actually running as compiled code. Taking parts of algorithms and switching from for loops to array operations that execute as compiled code on the server frequently saw performance gains by a factor of 5-40.

3. Parallel processing!

Some problems are very amenable to parallel processing. This can either mean taking advantage of multi-core CPUs, working in a distributed computing environment (aka hadoop) or even GPU processing. Off the top of my head, I'm not sure how helpful any of those options will be to your program. I'm going to guess that this isn't important enough to be worth the time it takes to re-write this algorithm for some advance parallel processing but hey, you never know.

Summary

These are the steps I would go through if I had code that I needed to run quickly that was simply too slow. How much time you spend actually optimizing things always depends on how important the code is, of course. But ultimately you have those three options: make the code faster, figure out how to get it to run compiled, or throw lots of computing power at the problem. In your particular case your problem will likely allow for only some optimization via smarter algorithms, so if you really need this to go fast you may have to start looking at options 2 & 3.