CODEWITHSUNDEEP
pythonfor-loopnested
mismaah
mismaah

Reputation: 356

Alternative to nested for loops

Take this code for example

#Find all combinations of five positive integers whose reciprocals sum to 1 under a limit
limit = 30
none = True
reciprocals5 = []
for x in range(1,limit):
    for y in range(1,limit):
        for z in range(1,limit):
            for a in range(1,limit):
                for b in range(1,limit):
                    if(x!=y and x!=z and x!=a and x!=b and y!=z and y!=a and y!=a and y!=b and z!=a and z!=b and a!=b):
                        if(1/x + 1/y + 1/z + 1/a + 1/b == 1):
                            reciprocals5.append([x,y,z,a,b])
                            none = False

If I had to find all 6 positive integer combinations, I would have to add another loop and so on. Lets say I want to find all N positive integer combinations. Since I cannot create N nested for loops, what is the alternative?

Upvotes: 1

Views: 1266

Answers (4)

filbranden
filbranden

Reputation: 8898

Since I cannot create N nested for loops, what is the alternative?

Recursion!

Have a function taking extra arguments, such as the number of terms to sum and the target number, then in its implementation call itself again with one fewer term.

Your stopping condition is when the number of terms to sum is zero. In that case, if the target number to reach is zero, it means you found a valid sum. If it's non-zero, it means you didn't. (Similarly, you could do the last check at 1 term left, checking whether you can pick a final number to match it.)

Since you only need to find sets of distinct numbers that sum up to one, you can assume x > y > z > a > b (or the opposite ordering), to make sure you're not finding the same sequence over and over again, just in a different order.

Also, iterating down from the limit means the reciprocals will grow as you proceed in the iteration. Which also means you can stop looking once the sum goes past one (or the target gets negative), which should help you quickly prune loops that won't ever yield new values.

Finally, Python also supports fractions, which means you can make these calculations with exact precision, without worrying about the rounding issues of floats.

Putting it all together:

from fractions import Fraction

def reciprocal_sums(n=5, limit=30, target=1, partial=()):
    if n == 0:
        if target == 0:
            yield partial
        return
    for i in range(limit, 0, -1):
        new_target = target - Fraction(1, i)
        if new_target < 0:
            return
        yield from reciprocal_sums(
            n - 1, i - 1, new_target, partial + (i,))

Testing it for n=5 (default):

>>> list(reciprocal_sums())
[(30, 20, 12, 3, 2),
 (30, 20, 6, 4, 2),
 (30, 10, 6, 5, 2),
 (28, 21, 12, 3, 2),
 (28, 21, 6, 4, 2),
 (28, 14, 7, 4, 2),
 (24, 12, 8, 4, 2),
 (20, 12, 6, 5, 2),
 (20, 6, 5, 4, 3),
 (18, 12, 9, 4, 2),
 (15, 12, 10, 4, 2)]

For n=4:

>>> list(reciprocal_sums(4))
[(24, 8, 3, 2),
 (20, 5, 4, 2),
 (18, 9, 3, 2),
 (15, 10, 3, 2),
 (12, 6, 4, 2)]

And n=6:

>>> list(reciprocal_sums(6))
[(30, 28, 21, 20, 3, 2),
 (30, 24, 20, 8, 4, 2),
 (30, 24, 10, 8, 5, 2),
 (30, 20, 18, 9, 4, 2),
 (30, 20, 15, 10, 4, 2),
 (30, 18, 10, 9, 5, 2),
 (30, 12, 10, 5, 4, 3),
 (28, 24, 21, 8, 4, 2),
 (28, 21, 20, 6, 5, 2),
 (28, 21, 18, 9, 4, 2),
 (28, 21, 15, 10, 4, 2),
 (28, 20, 14, 7, 5, 2),
 (28, 14, 12, 7, 6, 2),
 (28, 14, 7, 6, 4, 3),
 (24, 20, 12, 8, 5, 2),
 (24, 20, 8, 5, 4, 3),
 (24, 18, 9, 8, 6, 2),
 (24, 15, 10, 8, 6, 2),
 (24, 12, 8, 6, 4, 3),
 (20, 18, 12, 9, 5, 2),
 (20, 18, 9, 5, 4, 3),
 (20, 15, 12, 10, 5, 2),
 (20, 15, 10, 5, 4, 3),
 (18, 15, 10, 9, 6, 2),
 (18, 12, 9, 6, 4, 3),
 (15, 12, 10, 6, 4, 3)]

This solution is pretty fast. Running on a Snapdragon 845 ARM CPU:

%timeit list(reciprocal_sums(4)) 
365 ms ± 5.74 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit list(reciprocal_sums(5))
1.94 s ± 8.93 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit list(reciprocal_sums(6))
8.26 s ± 56.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

The ordering (lowering the limit at each level) together with pruning the last levels after going above the target will make this solution much faster than ones that evaluate all possible permutations or combinations.

Upvotes: 2

Prashant Kumar
Prashant Kumar

Reputation: 2092

Try this :

import itertools
myList = []
for combination in itertools.product(range(10), repeat=6):
    myList.append(''.join(map(str, combination)))

This will create a list of 6 digit integers in str format. You can type cast then easily.

Upvotes: 0

alec
alec

Reputation: 6112

You can use itertools.permutations. 

import itertools

reciprocals = []
for x in itertools.permutations(range(1, limit), N):
    if sum(1/i for i in x) == 1:
        reciprocals.append(x)

Upvotes: 0

Joran Beasley
Joran Beasley

Reputation: 113940

itertools.product(list(range(N)),repeat=N)

maybe what you want

Upvotes: 0

Related Questions