python - 在没有追溯过滤的情况下创建对每个元素都有限制的组合

Question

我需要创建列表的所有组合，但每个元素都有上下边界(每个数字增加 +2)。

例如 n=4:从 [0, 1, 2, 3](下边界)到 [0,2,4,6](上边界)的所有组合应该导致:

[[0, 1, 2, 3],
 [0, 1, 2, 4],
 [0, 1, 2, 5],
 [0, 1, 2, 6],
 [0, 1, 3, 4],
 [0, 1, 3, 5],
 [0, 1, 3, 6],
 [0, 1, 4, 5],
 [0, 1, 4, 6],
 [0, 2, 3, 4],
 [0, 2, 3, 5],
 [0, 2, 3, 6],
 [0, 2, 4, 5],
 [0, 2, 4, 6]]

直接的解决方案是使用 itertools.combinations(range(2*n-1),n) 然后过滤掉所有无效的。但这首先会产生大量无效组合，然后通过遍历所有的过滤器进一步减慢速度。就我而言，这对于大 n 来说效率太低了。

我需要一个解决方案，它甚至不会尝试为每个数字循环得比可能的更高，并且只在每个数字的边界内创建组合。

我确定有一个带有嵌套循环或回溯的简单解决方案，但我找不到。

Answer 1

这是一个使用递归的解决方案:

def n_increasing(n, start=0, end=0): 
    if n == 0: 
        yield [] 
        return 
    for choice in range(start, end+1): 
        for remaining in n_increasing(n-1, choice+1, end+2):
            yield [choice, *remaining] 

用法:

>>> list(n_increasing(4))
[[0, 1, 2, 3],
 [0, 1, 2, 4],
 [0, 1, 2, 5],
 [0, 1, 2, 6],
 [0, 1, 3, 4],
 [0, 1, 3, 5],
 [0, 1, 3, 6],
 [0, 1, 4, 5],
 [0, 1, 4, 6],
 [0, 2, 3, 4],
 [0, 2, 3, 5],
 [0, 2, 3, 6],
 [0, 2, 4, 5],
 [0, 2, 4, 6]]