Обход дерева или что?

Question

В Python я пишу модуль обработки естественного языка и не могу понять, как кодировать функцию для выполнения следующих действий. Вход: список частей речи (POS), полученных из введенного предложения в виде коротких строк. Некоторые элементы в списке сами являются списками, потому что эта часть программы не знает, какую часть речи выбрать из двух или более возможных. например конкретное предложение из шести слов приводит к ["DET", "NOUN", ["VERB", "NOUN"], "CONJ", ["ADJ", "ADV", "NOUN"], "ADV"] то есть первое слово определенно DET 2-е слово определенно НОУН третье слово может быть VERB или NOUN 4-е слово, безусловно, является CONJ 5-е слово может быть ADJ, ADV или NOUN 6-е слово определенно является ADV.

Итак, ВХОД = ["DET", "NOUN", ["VERB", "NOUN"], "CONJ", ["ADJ", "ADV", "NOUN"], "ADV"]

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

[["DET", "NOUN", "NOUN", "CONJ", "NOUN", "ADV"],
 ["DET", "NOUN", "NOUN", "CONJ", "ADV", "ADV"],
 ["DET", "NOUN", "NOUN", "CONJ", "ADJ", "ADV"],
 ["DET", "NOUN", "VERB", "CONJ", "NOUN", "ADV"],
 ["DET", "NOUN", "VERB", "CONJ", "ADV", "ADV"],
 ["DET", "NOUN", "VERB", "CONJ", "ADJ", "ADV"]]

Предложения могут быть длиной от одного до n слов. Каждое слово может содержать от одной до n частей речи.

Answer 1

Обратите внимание на модуль itertools и связанные с ним рецепты. Похоже, вы хотите рассмотреть декартово произведение всех возможных POS-назначений. Это легко сделать, хотя удобнее, чтобы все элементы INPUT были списками, даже если они только списки из одного. В любом случае:

>>> import itertools
>>> 
>>> INPUT = ["DET", "NOUN", ["VERB", "NOUN"], "CONJ", ["ADJ", "ADV", "NOUN"], "ADV"]
>>> 
>>> I = [[kind] if type(kind) != list else kind for kind in INPUT]
>>> I
[['DET'], ['NOUN'], ['VERB', 'NOUN'], ['CONJ'], ['ADJ', 'ADV', 'NOUN'], ['ADV']]

так что это те возможности, которые мы хотим выбрать. Вот для чего itertools.product:

>>> possible_assignments = list(itertools.product(*I))
>>> possible_assignments
[('DET', 'NOUN', 'VERB', 'CONJ', 'ADJ', 'ADV'), ('DET', 'NOUN', 'VERB', 'CONJ', 'ADV', 'ADV'), ('DET', 'NOUN', 'VERB', 'CONJ', 'NOUN', 'ADV'), ('DET', 'NOUN', 'NOUN', 'CONJ', 'ADJ', 'ADV'), ('DET', 'NOUN', 'NOUN', 'CONJ', 'ADV', 'ADV'), ('DET', 'NOUN', 'NOUN', 'CONJ', 'NOUN', 'ADV')]

что, если я вас понимаю, то, что вы хотите. Ну, это кортежи, а не списки, но это не должно иметь значения.

---