如何创建蛮力程序来生成列表的所有可能组合，直到上限？

Question

我必须创建一个函数，该函数接受一个上限列表并返回一个列表，其中包含所有可能的组合，直到上限。例如，输入列表[1，1，2]将产生：

[ [ 0 , 0 , 0 ] , 
[ 0 , 0 , 1 ] , 
[ 0 , 0 , 2 ] , 
[ 0 , 1 , 0 ] , 
[ 0 , 1 , 1 ] ,
[ 0 , 1 , 2 ] , 
[ 1 , 0 , 0 ] , 
[ 1 , 0 , 1 ] , 
[ 1 , 0 , 2 ] , 
[ 1 , 1 , 0 ] , 
[ 1 , 1 , 1 ] , 
[ 1 , 1 , 2 ] , ]

到目前为止，我有这个：

def bounded_lists(upper_bound):
    start = [0] * len(upper_bound)
    print(start)
    while start != upper_bound:
        for i in range(1, len(upper_bound)+ 1):
            while start[-i] < upper_bound[-i]:
                start[-i] = start[-i] + 1
                print(start)
            start[-i] = 0
        break

但是，它仅返回：

[0, 0, 0]
[0, 0, 1]
[0, 0, 2]
[0, 1, 0]
[1, 0, 0]

Answer 1

您可以使用标准库 itertools

from itertools import product

def bounded_lists(upper_bound):
    return list(product(*[range(ub + 1) for ub in upper_bound]))

这是这样的：

>>> bounded_lists([1, 1, 2])
[(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 1, 0), (0, 1, 1), (0, 1, 2), (1, 0, 0), (1, 0, 1), (1, 0, 2), (1, 1, 0), (1, 1, 1), (1, 1, 2)]

更新：如果您不满意使用其他库，则可以尝试递归执行。

def bounded_lists(upper_bound):
    result = []

    if len(upper_bound)== 0:
        result = []
    elif len(upper_bound)==1:
        result = [[i] for i in range(upper_bound[0] + 1)]
    else:
        first_bound = upper_bound[0]
        other_bound = upper_bound[1:]
        for i in range(first_bound + 1):
            for lst in bounded_lists(other_bound):
                result.append([i] + lst)
    return result