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

问题描述 投票:1回答:3

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

  • 接受长度为n和的正整数列表作为参数
  • 返回长度为n的所有列表的列表,其中包含具有以下属性的非负整数: 对于列表lst,它认为对于所有指数我,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]]

我无法理解如何包含缺失的列表,任何帮助都会很棒。

python algorithm list iterator cartesian-product
3个回答
3
投票

这是一个选项:

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)))

2
投票

你应该看看itertools packagelist comprehensions

然后一个解决方案是:

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

0
投票

你可以使用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)]
© www.soinside.com 2019 - 2024. All rights reserved.