遍历 Int 集的算法

Question

我不确定在这里问这样的问题是否合适。我会试一试。

问题:

假设val threshold: Int和 val size: Int .

我正在寻找一种有效的算法来遍历所有可能的 x: Set[Int]其中 x.sum < threshold和 x.size == n .只应考虑大于 0 的整数。这当然是有限数量的可能性。

我已经尝试开发一个，但即使是较小的输入也需要很长时间。

提前致谢。

Answer 1

您可以很容易地递归生成它们。下面是用 Python 编写的一些代码，但它应该直接转换为 Scala。

def sets(n, threshold, atleast=1):
    if threshold <= n * (n + atleast * 2 - 1) // 2: return
    if n == 0:
        yield []
        return
    for i in xrange(atleast, threshold):
        for s in sets(n - 1, threshold - i, i + 1):
            yield [i] + s

print list(sets(4, 15))