Arbitrary number of nested loops dependent on the previous loop in Python

Question

I'm trying to figure out how to iterate over an arbitrary number of loops where each loop depends on the most recent outer loop. The following code is an example of what I want to do:

def function(z):
    n = int(log(z))
    tupes = []
    for i_1 in range(1, n):
        for i_2 in range(1, i_1):
            ...
                ...
                    ...
                        for i_n in range(1, i_{n - 1}):
                            if i_1*i_2*...*i_n > z:
                                tupes.append((i_1, i_2,..., i_n))
    return tupes

While I'd like this to work for any z > e**2, it's sufficient for it to work for zs up to e**100. I know that if I take the Cartesian product of the appropriate ranges that I'll end up with a superset of the tuples I desire, but I'd like to obtain only the tuples I seek.

If anyone can help me with this, I'd greatly appreciate it. Thanks in advance.

Answer 1

Combinations can be listed in ascending order; in fact, this is the default behavior of itertools.combinations.

The code:

for i1 in range(1,6):
    for i2 in range(1,i1):
        for i3 in range(1,i2):
            print (i3, i2, i1)

# (1, 2, 3)
# (1, 2, 4)
# ...
# (3, 4, 5)

Is equivalent to the code:

from itertools import combinations

for combination in combinations(range(1,6), 3):
    print combination

# (1, 2, 3)
# (1, 2, 4)
# ...
# (3, 4, 5)

Using the combinations instead of the Cartesian product culls the sample space down to what you want.

Answer 2

The logic in your question implemented recursively (note that this allows for duplicate tuples):

import functools

def f(n, z, max_depth, factors=(), depth=0):
    res = []
    if depth == max_depth:
        product = functools.reduce(lambda x, y: x*y, factors, 1)
        if product > z:
            res.append(factors)
    else:
        for i in range(1, n):
            new_factors = factors + (i,)
            res.extend(f(i, z, factors=new_factors, depth=depth+1, max_depth=max_depth))
    return res

z = np.e ** 10
n = int(np.log(z))

print(f(n, z, max_depth=8))

yields

[(8, 7, 6, 5, 4, 3, 2, 1),
 (9, 7, 6, 5, 4, 3, 2, 1),
 (9, 8, 6, 5, 4, 3, 2, 1),
 (9, 8, 7, 5, 4, 3, 2, 1),
 (9, 8, 7, 6, 4, 3, 2, 1),
 (9, 8, 7, 6, 5, 3, 2, 1),
 (9, 8, 7, 6, 5, 4, 2, 1),
 (9, 8, 7, 6, 5, 4, 3, 1),
 (9, 8, 7, 6, 5, 4, 3, 2)]

Answer 3

As zondo suggested, you'll need to use a function and recursion to accomplish this task. Something along the lines of the following should work:

def recurse(tuplesList, potentialTupleAsList, rangeEnd, z):
    # No range to iterate over, check if tuple sum is large enough
    if rangeEnd = 1 and sum(potentialTupleAsList) > z:
        tuplesList.append(tuple(potentialTupeAsList))
        return
    for i in range(1, rangeEnd):
        potentialTupleAsList.append(i)
        recurse(tuplesList, potentialTupleAsList, rangeEnd - 1, z)
        # Need to remove item you used to make room for new value
        potentialTupleAsList.pop(-1)

Then you could call it as such to get the results:

l = []
recurse(l, [], int(log(z)), z)
print l