CODEWITHSUNDEEP
pythonloops
philomathic_life
philomathic_life

Reputation: 514

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

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.

Upvotes: 5

Views: 1812

Answers (4)

marc_r
marc_r

Reputation: 160

Your innermost loop can (if reached at all) only go over range(1, 1). Since the endpoint is not included, the loop will not iterate over any values. The shortest implementation of your function is thus:

def function(z):
    return []

If you are content with tuples of length smaller than n, then I propose the following solution:

import math

def function(z):

    def f(tuples, loop_variables, product, end):
        if product > z:
            tuples.append(loop_variables)

        for i in range(end - 1, 0, -1):
            f(tuples, loop_variables + (i,), product * i, i)
           
    n = int(math.log(z)) 
    tuples = []
    f(tuples, (), 1, n)
    return tuples

The time complexity is not good though: With n nested loops over O(n) elements, we are on the order of n**n steps.

Upvotes: 0

Alex
Alex

Reputation: 19104

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)]

Upvotes: 1

Jared Goguen
Jared Goguen

Reputation: 9010

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.

Upvotes: 4

willwolfram18
willwolfram18

Reputation: 1887

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

Upvotes: 1

Related Questions