一次复制并修改深度嵌套列表一个元素

Question

我目前正在开发一个项目，该项目应该生成一个有向图，其中每个顶点都是一个深度嵌套的列表。 为了启动这个过程，它需要一个深度嵌套的列表，然后应该复制和修改该列表。 例如：

Initial vertex: [[1, 1], [1, 1]]
Resulting vertices: [[1, 1], [1, 0]] x 4, [[1, 1], [0, 0]] x 2, [[0, 0], [0, 0]]

Initial vertex: [[1, 0], [1, 1]]
Resulting vertices: [[1, 0], [0, 0]], [[1, 0], [1, 0]] x 2, [[1, 1], [0, 0]] x 2, [[0, 0], [0, 0]]

每个列表都应该被视为对称：

[[1, 0], [0, 0]] == [[0, 1], [0, 0]] == [[0, 0], [1, 0]] == [[0, 0], [0, 1]]

如果生成的顶点等于已存在的顶点的顶点或对称于一，则仅创建到已存在的顶点的边。

我目前正在尝试使用递归算法来解决这个问题。问题是我需要复制父顶点的整个嵌套列表并仅更改相关的子列表，对此我还没有找到解决方案。 为了检查两个顶点是否相等，我首先递归地对每个列表进行排序，然后将排序后的列表相互比较，这似乎有效。

def sort(lst):
    ordered = []
    for ele in sorted(lst):
        if isinstance(ele, list):
            ele = sort(ele)
        ordered.append(ele)
    return ordered

将每个值设置为 0 的朴素递归算法：

def destroy(lst):
    failed = []
    for ele in lst:
        if isinstance(ele, list):
            ele = destroy(ele)
        else:
            ele = 0
        failed.append(ele)
    return failed

它应该如何工作：

输入是深度为 n 的嵌套列表（此处 n=2）：

[[1, 1], [1, 1]]

该算法应该遍历这些嵌套列表，并首先将最深列表（深度 n）中的每个 1 依次设置为 0。

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

遍历完所有深度为 n 的列表后，它会继续遍历所有深度为 n-1 的列表。由于这些列表包含列表或嵌套列表，因此应该复制这些列表的结构。副本只能包含零。

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

当 n-1 完成后，它应该上升到深度 n-2 并继续。在此示例中，n-2 是顶层，因此只会导致

[[0, 0], [0, 0]]

之后，我可以通过首先递归排序然后检查相等性以“合并”它们来比较所有新创建的嵌套列表。

我发现，可以使用 itertools.combinations_with_replacement 来生成所有唯一的嵌套列表。剩下的问题是，换句话说，它生成了图形的所有顶点，但我缺少过渡/边缘。

states = [0, 1]
depth = 2
for _ in range(depth):
    states = list(map(list, itertools.combinations_with_replacement(states, states)))

Answer 1

我想我已经找到了一种时间复杂度低的良好工作算法。生成的值稍后通过自定义 eq 进行比较，当我不再需要它们时，可以使用集合消除重复项。

我将在这里发布我的算法，以防将来有人偶然发现同样的问题。

for i in range(depth + 1):
    binaryAddr = itertools.product([0, 1], repeat=i)
    for addr in binaryAddr:
        child = numpy.copy(parent)
        child[addr] = numpy.zeros_like(child[addr])
        yield child

一个小解释：由于我的嵌套列表的组成，我可以使用二进制地址来寻址每个值。 Numpy 提供了将列表作为元素地址提供的可能性，因此我只需将所有必要的地址生成为列表，并修改特定地址处父级的副本。将值设置为 0 并保持结构是通过使用 Zeros_like 完成的。