python - 生成每个元素遵循特定条件的 n 大小向量的所有可能组合

Question

我有一个长度为 r 的列表 d ，使得 d = (d_1, d_2,..., d_r) 。 我想生成长度为 r 的所有可能的向量，使得 for any i (from 0 to r), v_i is between 0 and d_i .

例如，

if r =2 and d= (1,2), v_1 can be 0 or 1 and v_2 can be 0,1 or 2. 

因此有 6 个可能的向量: [0,0] , [0,1], [0,2], [1,0] , [1,1], [1,2]

我研究了 Itertools 和组合，我有一种感觉，我将不得不使用递归，但我还没有设法解决它，并希望得到一些帮助或建议以正确的方向。

编辑: 我为我的问题编写了以下代码，它有效，但是我以一种非常低效的方式做到了这一点:忽略条件并生成所有可能的向量，然后修剪无效的向量。我拿了最大的d_i并生成大小为 r 的所有向量来自(0,0,...0)一直到(max_d_i,max_d_i,....max_d_i)然后剔除那些无效的。

代码:

import itertools
import copy
def main(d):
    arr = []
    correct_list =[]
    curr = []
    r= len(d)
    greatest = max(d)
    for i in range(0,greatest+1):
        arr = arr + [i]
    #all_poss_arr is a list that holds all possible vectors of length r from (0,0,...,0) to (max,max,...,max)
    # for example if greatest was 3 and r= 4, all_poss_arr would have (0,0,0,0), then (0,0,0,1) and so on,
    #all the way to (3,3,3,3)
    all_poss_arr = list(itertools.product(arr,repeat = r))    
    #Now I am going to remove all the vectors that dont follow the v_i is between 0 and d_i
    for i in range(0,len(all_poss_arr)):
        curr = all_poss_arr[i]
        cnt = 0
        for j in range(0,len(curr)):
            if curr[j] <= d[j]:
                cnt = cnt +1
        if cnt == r:
            curr = list(curr)
            currcopy = copy.copy(curr)
            correct_list = correct_list + [currcopy]
            cnt =0
    return correct_list

如果有人知道更好的方法，请告诉我，非常感谢。

Answer 1

你基本上想要一个笛卡尔积。我将演示一种基本的、实用的和迭代的方法。

给定

import operator as op
import functools as ft
import itertools as it


def compose(f, g):
    """Return a function composed of two functions."""
    def h(*args, **kwargs):
        return f(g(*args, **kwargs))
    return h


d = (1, 2)

代码

选项 1:基本 - 手动解包

list(it.product(range(d[0] + 1), range(d[1] + 1)))
# [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2)]

选项 2:功能 - 自动映射

def vector_combs(v):
    """Return a Cartesian product of unpacked elements from `v`."""
    plus_one = ft.partial(op.add, 1)
    range_plus_one = compose(range, plus_one)
    res = list(it.product(*map(range_plus_one, v)))
    return res


vector_combs(d)
# [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2)]

选项 3:迭代 - 范围复制(推荐)

list(it.product(*[range(x + 1) for x in d]))
# [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2)]

<小时/>

详细信息

选项 1

基本思想如选项 1 所示:

• 创建 Cartesian product使用一系列修改后的范围。

请注意，每个范围都是手动递增并作为d中的索引传入。我们使用最后一个选项自动执行这些限制。

选项 2

我们应用函数式方法来处理各种参数和函数:

• Partial add() 函数的 1 参数。这将返回一个可以增加任意数字的函数。
• 让我们通过composition将此函数传递到范围中。这允许我们修改范围函数，自动递增传入的整数。
• 最后我们map后一个函数作用于元组d中的每个元素。现在d适用于任何长度的r。

示例(d = (1, 2, 1), r = 3):

vector_combs((1, 2, 1))
# [(0, 0, 0),
#  (0, 0, 1),
#  (0, 1, 0),
#  (0, 1, 1),
#  (0, 2, 0),
#  (0, 2, 1),
#  (1, 0, 0),
#  (1, 0, 1),
#  (1, 1, 0),
#  (1, 1, 1),
#  (1, 2, 0),
#  (1, 2, 1)]

选项 3

也许最优雅的是，只需使用列表理解来创建 r 范围。 ;)