Looping over multiple ranges in "BFS" order?

Question

Let's say for k=3 and n=4, then one could simply loop over the k different n-ranges like

for a in range(4):
  for b in range(4):
    for c in range(4):
      print((a, b, c))

The problem is that this goes all the way through the last n-range quickly, and takes forever to go through the first n-range. I want a more balanced ordering of looping through the same ranges, where each range is gone through at the same pace. Kind of like the difference between DFS and BFS.

For example, the ordering of the tuples to be more like

(0, 0, 0)
(1, 0, 0)
(0, 1, 0)
(0, 0, 1)
(1, 1, 0)
(0, 1, 1)
(1, 0, 1)
(2, 0, 0)
(0, 2, 0)
(0, 0, 2)
(1, 1, 1)
(2, 1, 0)
(1, 2, 0)
(0, 2, 1)
(0, 1, 2)
(2, 0, 1)
(1, 0, 2)
(3, 0, 0)
(0, 3, 0)
(0, 0, 3)
etc.

To be clear, I'd like a generator function k_tuples_of_range_n(k, n) that spits out the tuples in that "BFS" ordering. And the function should be efficient (taking up at most O(k) space and time to generate each tuple).

Anyone know if there's a name for this ordering, or an elegant solution?

Edit: To be clear, there's no explicit tree or BFS happening. I just call it "BFS" order to evoke that one is evenly exploring all the ranges (as opposed to going through one range and neglecting the others). If I had to say concretely how the tuples are ordered: each tuple t is ascendingly ordered primarily by sum(t), and secondarily by max(t). So (3, 0, 0) comes after (1, 1, 0) because it has a higher sum. (3, 0, 0) comes after (1, 1, 1) because it has a higher max.

Answer 1

Let's define the number of distinct values of one member of a result tuple. In the example, =4. And define the number of tuple members as . Then there are different tuples possible.

You could use a modulo counter to produce integers in the range [0, ). It could use the formula := ( + offset) % modulo, where the two parameters are primes. This is a simple case of a Linear congruential generator.

The modulo prime should be chosen to be not less than , and the offset prime could be a lesser one.

Here is an implementation:

def primes_sieve(limit):
    a = [True] * limit
    a[0] = a[1] = False
    for i, isprime in enumerate(a):
        if isprime:
            yield i
            for n in range(i * i, limit, i):
                a[n] = False


def get_lcg_params(count):
    minc = count // 3
    c = 0
    # choose prime values for the modulo and offset
    for prime in primes_sieve(2*count):
        if not c and prime > minc:
            c = prime
        if prime > count:
            return c, prime


def lcg(offset, modulo):
    value = 0
    while True:
        yield value
        value = (value + offset) % modulo
        if not value:
            break
    

def to_base(value, base, num_digits):
    for i in range(num_digits):
        yield value % base
        value //= base


def gen(n, m):
    count = n**m
    for value in lcg(*get_lcg_params(count)):
        if value < count:
            yield tuple(to_base(value, n, m))


# Example run:
for value in gen(4, 3):
    print(value)

This particular example run will output:

(0, 0, 0)
(3, 1, 1)
(2, 3, 2)
(2, 0, 0)
(1, 2, 1)
(0, 0, 3)
(0, 1, 0)
(3, 2, 1)
(2, 0, 3)
(2, 1, 0)
(1, 3, 1)
(0, 1, 3)
(0, 2, 0)
(3, 3, 1)
(2, 1, 3)
(2, 2, 0)
(1, 0, 2)
(0, 2, 3)
(0, 3, 0)
(3, 0, 2)
(2, 2, 3)
(2, 3, 0)
(1, 1, 2)
(0, 3, 3)
(0, 0, 1)
(3, 1, 2)
(2, 3, 3)
(2, 0, 1)
(1, 2, 2)
(0, 1, 1)
(3, 2, 2)
(2, 1, 1)
(1, 3, 2)
(1, 0, 0)
(0, 2, 1)
(3, 3, 2)
(3, 0, 0)
(2, 2, 1)
(1, 0, 3)
(1, 1, 0)
(0, 3, 1)
(3, 0, 3)
(3, 1, 0)
(2, 3, 1)
(1, 1, 3)
(1, 2, 0)
(0, 0, 2)
(3, 1, 3)
(3, 2, 0)
(2, 0, 2)
(1, 2, 3)
(1, 3, 0)
(0, 1, 2)
(3, 2, 3)
(3, 3, 0)
(2, 1, 2)
(1, 3, 3)
(1, 0, 1)
(0, 2, 2)
(3, 3, 3)
(3, 0, 1)
(2, 2, 2)
(1, 1, 1)
(0, 3, 2)