[FIXED] Avoid three nested loops to search for all numbers not in a list

Issue

I want to find all the numbers that are not in a list and are equal to the following formula : x + x_max * y + x_max * y_max * z, where (x_max, y_max) are parameters and (x, y, z) can vary in a restricted set. I also want to know the values of (x, y, z) that I need to obtain each number.

I have succeeded to do this with the following code but it is currently extremely slow due to the three-nested loops. I am looking for a faster solution (maybe using NumPy arrays?).

What my code is actually doing with an extremely low speed (but works):

import numpy as np

x_max, y_max, z_max = 180, 90, 90

numbers = np.random.randint(x_max * y_max * z_max, size=1000)
results = np.array([[0, 0, 0, 0]]) # Initializes the array

for x in range(0, x_max):
    for y in range(0, y_max):
        for z in range(0, z_max):
            result = x + y * x_max + z * x_max * y_max
            if (result not in numbers):
                results = np.append(results, [[x, y, z, result]], axis=0)

# Initial line is useless
results = np.delete(results, (0), axis=0)

Solution

Your nested loop and the calcuation:

for x in range(0, x_max):
    for y in range(0, y_max):
        for z in range(0, z_max):
            result = x + y * x_max + z * x_max * y_max

simply calculate all integers between 0 and x_max * y_max * z_max. And all the integers are unique as well: no integer is calculated twice.

That fact makes this a lot easier:

values = np.arange(x_max * y_max * z_max)
results = np.setdiff1d(values, numbers)

This will give you all the integers that have been calculated and are not in the numbers exclusion list.

Now you only miss the input x, y and z values. These, though, can be calculated from the actual results with some straightforward modulo arithmetic:

z = results // (x_max * y_max)
rem = results % (x_max * y_max)
y = rem // x_max
x = rem % x_max

Now you can stack it all nicely together:

results = np.array([x, y, z, results])

You can tweak your results array if needs be, e.g.:

results = results.T  # simple transpose
results = np.sort(results, axis=1)  # sort the inner list

I used the above to compare the output from this calculation with that of the triple-nested loop calculation. The results were indeed equal.

Answered By - 9769953