以“BFS”顺序循环多个范围？

Question

假设对于

k=3

和

n=4

，那么可以简单地循环遍历

k

不同的

n

范围，例如

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

问题在于，这会快速遍历最后一个

n

范围，并且需要永远遍历第一个

n

范围。我想要更平衡地循环遍历相同的范围，其中每个范围都以相同的速度遍历。有点像 DFS 和 BFS 之间的区别。

例如，元组的排序更像是

(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.

要明确的是，我想要一个生成器函数

k_tuples_of_range_n(k, n)

，它可以按“BFS”顺序吐出元组。并且该函数应该是高效的（最多占用 O(k) 空间和时间来生成每个元组）。

有人知道这个排序是否有一个名称，或者一个优雅的解决方案？

编辑：需要明确的是，没有发生显式的树或 BFS。我只是将其称为“BFS”顺序，以唤起人们均匀地探索所有范围（而不是通过一个范围而忽略其他范围）。如果我必须具体说明元组是如何排序的：每个元组

t

主要按

sum(t)

升序排序，其次按

max(t)

排序。所以

(3, 0, 0)

排在

(1, 1, 0)

之后，因为它的总和更高。

(3, 0, 0)

位于

(1, 1, 1)

之后，因为它具有更高的最大值。

Answer 1

让我们定义 𝑛 结果元组一个成员的不同值的数量。在该示例中，𝑛=4。并将元组成员的数量定义为𝑚。那么就有可能有 𝑛^𝑚 不同的元组。

您可以使用模计数器来生成 [0, 𝑛^𝑚) 范围内的整数。它可以使用公式 𝑥 := (𝑥 + offset) % modulo，其中两个参数是素数。这是一个简单的线性同余生成器。

模素数应选择不小于𝑛^𝑚，偏移素数可以更小。

这是一个实现：

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)

这个特定的示例运行将输出：

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