从任意深度列表的嵌套列表创建所有组合

Question

我编写了一个递归函数，它迭代生成具有 N 个原子的六角晶格的可能图案。该函数首先在晶格上选择一个点，删除所有太靠近原始点的点，然后将下一个原子放置在剩余的有效位置之一上。

此函数 return 是一个嵌套的列表列表，具体取决于要放置的原子数。

例如对于两个原子，它会 return 一个像这样的列表：配置 = [[site1, [valid_sites]], [site2, [valid_sites]], ...]

对于三个原子：配置 = [[site1, [site2_1,[valid_sites]]],[site1, site2_2,[valid_sites]], ...]

高达任意深度的原子数。每个站点对象都是一个 2d-numpy 数组。

现在我需要的是一种从这个嵌套列表中产生所有有效配置的可迭代的方法：

[[site1, valid_sites[0]], [site1, valid_sites[1]], ... [site2,valid_sites[0]]]

我试过 itertools.product() 但这有几个问题。在 N=2 的情况下，它将 site1 视为可迭代对象，并通过拆分向量 (site1[0], valid_sites[0]) 来生成笛卡尔积...一个简单的测试还表明它不会处理嵌套想要的方式。

我看了here and here，但这些似乎不需要深度为 N 的通用性，后者不编译列表。

这是我对递归函数的尝试：

def expand_list(configs,n,N):
if n<N:
expand_list(configs[n],n+1,N)
else:
return list(itertools.product(*configs))

最好尝试 "unnest" 循环然后做笛卡尔积吗？或者是否可以编写一些生成器函数来执行此操作？

Answer 1

所以你想做的是删除列表中的最后一项，然后用最后一项扩展列表，对吗？

这是一个递归的解决方案：

def expand_sites(sites):
    return [getsubsite(site) for site in sites]


def getsubsite(site):
    if len(site) == 1:
        return site
    else:
        return site[:1] + getsubsite(site[1])

这是一个非递归的解决方案：

def expand_sites(sites):
    return [getsubsite(site) for site in sites]


def getsubsite(site):
    site = site[:]  # copy the list
    while len(site[-1]) > 1:
       site.extend(site.pop())
    site.extend(site.pop())
    return site

以及改变原始列表而不是创建新列表的非递归解决方案：

def expand_sites(sites):
    for site in sites:
        while len(site[-1]) > 1:
            site.extend(site.pop())
        site.extend(site.pop())

从任意深度列表的嵌套列表创建所有组合

Creating all combinations from a nested list of lists of arbitrary depth

python

recursion

combinations

nested

list