[FIXED] Copy and modify deeply nested list one element at a time

Issue

I'm currently working on a project that is supposed to generate a directed graph in which each vertex is a deeply nested list. To kick off the process it requires a deeply nested list, which is then supposed to be copied and modified. For example:

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

Every list is supposed to be viewed as symmetric: [[1, 0], [0, 0]] == [[0, 1], [0, 0]] == [[0, 0], [1, 0]] == [[0, 0], [0, 1]]

If a generated vertex equals that of an already existing vertex or is symmetric to one, only an edge to the already existing vertex will be created.

I'm currently trying to solve this problem using a recursive algorithm. The problem is that I need to copy the entire nested list of the parent vertex and change only the relevant sub-list, for which I haven't found a solution yet. To check if two vertices are equal I'm first recursively ordering every list and then comparing the sorted lists to each other, which seems to work.

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

Naive recursive algorithm to set every value to 0:

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

How it's supposed to work:

Given as input is a nested list with depth n (here n=2): [[1, 1], [1, 1]] The algorithm is supposed to traverse these nested lists and first set every 1 in the deepest lists (depth n) to 0, one after another.

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

After it traverses all lists with depth n it continues with all lists with depth n-1. As these lists contain lists or nested lists, it's supposed to copy the structure of those lists. The copies should only contain zeros.

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

When n-1 is completed it should step up to depth n-2 and continue. In this example n-2 is the top level so it would only result in

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

Afterwards I can compare all newly created nested lists by first recursively sorting and then checking equality to "merge" them.

I found, that one can use itertools.combinations_with_replacement to generate all unique nested lists. The remaining problem is that, in other words, it generates all my vertices for the graph, but I'm missing the transitions/edges.

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

Solution

I think I've found a good working algorithm with low time complexity. Comparison of the generated values happens later on via a custom eq and duplicates are eliminated by using sets when I don't require them anymore.

I'll just post my algorithm here in case anyone in the future stumbles upon the same problem.

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

A small explanation: due to the composition of my nested list I can address every value using binary addresses. Numpy provides the possibility to feed a list as element address, so I just generate all necessary addresses as lists and modify a copy of the parent at the specific address. Setting values to 0 and keeping the structure is done by using zeros_like.

Answered By - UncaughtExceptionConnoisseur