创建一个包含上限所有子集的列表（但其中 lst[i] ≤ 上限[i]）

Question

我正在尝试构建一个函数：

接受长度为 n 的正整数列表作为参数并且
returns 所有长度为 n 的列表的列表，由非负整数组成，具有以下属性：
- 对于列表 lst 它认为对于所有索引 i，lst[i] ≤ upper bound[i]

例如，如果输入列表为 [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_list(ub):
    f = len(ub) * [0]
    l = ub
    res = [f]

    while res[-1] != l:
        res += [lex_suc1(res[-1], ub)]

    return res


def lex_suc1(lst, ub):
    res = lst[:]

    i = len(res) - 1
    while res[i] == ub[i]:
        res[i] = 0
        i -= 1

    res[i] = ub[i]
    return res

给出输出：

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

我不明白如何包含缺失的列表，如果有任何帮助就更好了。

Answer 1

这是一个选项：

from itertools import product

for lst in product(range(2), range(2), range(3)):
    print(lst)

请注意，您的列表 [1, 1, 2] 在此处翻译为 range(2), range(2), range(3)。

或更直接：

res = list(product(range(2), range(2), range(3)))
# [(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)]

甚至：

lst = [1, 1, 2]
res = list(product(*(range(i+1) for i in lst)))

Answer 2

你应该看看itertools package 和 list comprehensions.

那么一个解决方案是：

def f(upper_bounds):
    return list(itertools.product(*(range(ub+1) for ub in upper_bounds)))

Answer 3

您可以为此使用 itertools.product。

from  itertools import product
li = [1, 1, 2]

#Generate a list of possible numbers to generate the output from the given list
iters = [list(range(item+1)) for item in li]
#[[0, 1], [0, 1], [0, 1, 2]]

#Generate all possible combinations of these lists
print(list(product(*iters)))

输出将是。

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

创建一个包含上限所有子集的列表（但其中 lst[i] ≤ 上限[i]）

Create a list that contains all subsets from an upperbound (but where lst[i] ≤ upper bound[i])

python

algorithm

iterator

list

cartesian-product