How to spawn nested loops in python

Question

I've tried searching for an answer to this question and read a lot about decorators and global variables, but have not found anything that exactly makes sense with the problem at hand: I want to make every permutation of N-length using A-alphabet, fxn(A,N). I will pass the function 2 arguments: A and N. It will make dummy result of length N. Then, with N nested for loops it will update each index of the result with every element of A starting from the innermost loop. So with fxn(‘01’,4) it will produce

1111, 1110, 1101, 1100, 1011, 1010, 1001, 1000, 
0111, 0110, 0101, 0100, 0011, 0010, 0001, 0000

It is straightforward to do this if you know how many nested loops you will need (N; although for more than 4 it starts to get really messy and cumbersome). However, if you want to make all arbitrary-length sequences using A, then you need some way to automate this looping behavior. In particular I will also want this function to act as a generator to prevent having to store all these values in memory, such as with a list. To start it needs to initialize the first loop and keep initializing nested loops with a single value change (the index to update) N-1 times. It will then yield the value of the innermost loop.

The straightforward way to do fxn('01',4) would be:

for i in alphabet:
    tempresult[0] = i
    for i in alphabet:
        tempresult[1] = i
        for i in alphabet:
            tempresult[2] = i
            for i in alphabet:
                tempresult[3] = i
                yield tempresult

Basically, how can I extend this to an arbitrary length list or string and still get each nest loop to update the appropriate index. I know there is probably a permutation function as part of numpy that will do this, but I haven't been able to come across one. Any advice would be appreciated.

You want `itertools.permutations()`, in the standard library - or, more likely, `itertools.product('01', repeat=4)`. — Tim Peters, Oct 07 '13 at 21:35
Actually, I don't think `numpy` has an easy way to do this. You can use a recursive function that combines `tile` and `repeat` at each recursive step, but that doesn't seem very simple or efficient. — abarnert, Oct 07 '13 at 21:43

score 3 · Accepted Answer · edited May 23 '17 at 12:20

You don't actually want permutations here, but the cartesian product of alphabet*alphabet*alphabet*alphabet. Which you can write as:

itertools.product(alphabet, repeat=4)

Or, if you want to get strings back instead of tuples:

map(''.join, itertools.product(alphabet, repeat=4))

(In 2.x, if you want this to return a lazy iterator instead of a list, as your original code does, use itertools.imap instead of map.)

If you want to do this with numpy, the best way I could think of is to use a recursive function that tiles and repeats for each factor, but this answer has a better implementation, which you can copy from there, or apparently pull out of scikit-learn as sklearn.utils.extmath.cartesian, and then just do this:

cartesian([alphabet]*4)

Of course that gives you a 2D array of single-digit strings; you still need one more step to flatten it to a 1D array of N-digit strings, and numpy will slow you down there more than it speeds you up in the product calculation, so… unless you actually needed a numpy array anyway, I'd stick with itertools here.

score 0 · Answer 2 · answered Oct 07 '13 at 21:35

0

You can look to see how the itertools.permutations function works.

answered Oct 07 '13 at 21:35

Freddie

871
6
10

How to spawn nested loops in python

2 Answers2