Создание всех комбинаций из вложенного списка списков произвольной глубины

Question

Я написал рекурсивную функцию, которая итеративно генерирует возможные паттерны гексагональной решетки с N атомами. Функция сначала выбирает точку на решетке, удаляет все точки, которые были бы слишком близки к исходной точке, а затем помещает следующий атом на один из оставшихся допустимых сайтов.

Эта функция возвращает вложенный список списков в зависимости от количества атомов, которые должны быть размещены.

E.g. для двух атомов было бы возвращать список, как это: конфиги = [[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 он обрабатывает сайт1 как итерируемый и генерирует декартово произведение путем разбиения вектора (site1 [0], valid_sites [0]) ... Простой тест также показывает, что он не будет обрабатывать вложенность по желанию.

Я посмотрел here и 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())