python - 创建一个包含上限所有子集的列表(但其中 lst[i] ≤ 上限[i])

Question

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

• 接受长度为 n 的正整数列表作为参数，
• 返回所有长度为 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)))