как создать вложенный список неизвестного уровня, а затем получить его комбинации в виде отдельных списков - PullRequest
Новая
       26

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

0 голосов
/ 28 июня 2019

Я хочу получить все различные комбинации вложенного списка, уровень которого неизвестен.

Я искал решение, но все подобные проблемы не совсем то, что я ищу.

Учтите, что уровни могут быть очень глубокими, чем это, например, для внутренних уровней 5 или 6.

Основная проблема заключается в реализации обратного указателя для алгоритма CKY для получения всех возможных синтаксических деревьев, который представляет собой вложенный список с ДЕЙСТВИТЕЛЬНО неизвестными уровнями!!!

У меня есть обратный указатель, такой как: 

backpointer = {
    (0, 2, 'NP'): {
        (1, 'AD', 'NP')
    }, 
    (1, 3, 'X1'): {
        (2, 'NP', 'PA')
    }, 
    (1, 3, 'NP'): {
        (2, 'NP', 'NP')
    }, (0, 3, 'X1'): {
        (2, 'NP', 'PA'), 
        (1, 'DT', 'NP')
    }, 
    (2, 4, 'X2'): {
        (3, 'PA', 'VP')
    }, 
    (1, 4, 'S'): {
        (2, 'NP', 'X2'), 
        (3, 'X1', 'VP')
    }, 
    (0, 4, 'S'): {
        (2, 'NP', 'X2'), 
        (3, 'X1', 'VP')
    }
}

, от которого я отступаю от (0, 4, 'S'), рассматривая все возможные пути.

Мой текущий вывод похож на этот, который не классифицирован.: * 10101 

[
    (0, 4, 'S'), (0, 3, 'X1'), (0, 2, 'NP'), (0, 1, 'AD'), (1, 2, 'NP'), (2, 3, 'PA'), 
    (0, 1, 'DT'), (1, 3, 'NP'), (1, 2, 'NP'), (2, 3, 'NP'), (3, 4, 'VP'), (0, 2, 'NP'), 
    (0, 1, 'AD'), (1, 2, 'NP'), (2, 4, 'X2'), (2, 3, 'PA'), (3, 4, 'VP')
]

И я пытаюсь получить его как вложенный список, как показано ниже, чтобы классифицировать его 

[
    (0, 4, 'S'), 
    [
        (0, 2, 'NP'), (2, 4, 'X2'), (0, 1, 'AD'), (1, 2, 'NP'), (2, 3, 'PA'), (3, 4, 'VP')
    ], 
    [
        (0, 3, 'X1'), 
        (3, 4, 'VP'), 
        [
            (0, 2, 'NP'), (2, 3, 'PA'), (0, 1, 'AD'), (1, 2, 'NP')
        ], 
        [
            (0, 1, 'AD'), (1, 3, 'NP'), (1, 2, 'NP'), (2, 3, 'NP')
        ]
    ]
]

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

[
    (0, 4, 'S'), (0, 2, 'NP'), (2, 4, 'X2'), (0, 1, 'AD'), 
    (1, 2, 'NP'), (2, 3, 'PA'), (3, 4, 'VP')
]

[
    (0, 4, 'S'), (0, 3, 'X1'),(3, 4, 'VP'), (0, 2, 'NP'), 
    (2, 3, 'PA'), (0, 1, 'AD'), (1, 2, 'NP')
]

[
    (0, 4, 'S'), (0, 3, 'X1'),(3, 4, 'VP'), (0, 1, 'AD'), 
    (1, 3, 'NP'), (1, 2, 'NP'), (2, 3, 'NP')
]

Ответы [ 2 ]

1 голос
/ 28 июня 2019

IIUC, вы можете сначала написать рекурсивный генератор, чтобы "раскрутить" ваши вложенные list s. Вот быстрый и грязный подход 1 : 

def unnest(lst, append=False):
    chunk = []
    for x in lst:
        if isinstance(x, list):
            if chunk:
                yield chunk
            yield from unnest(x, True)
            chunk = []
        else:
            if append:
                chunk.append(x)
            else:
                yield [x]
    if chunk:
        yield chunk

lst = [0, 1, [2, 3, 4, [5, 6]], 7, [8, 9]]  # per original question
print(list(unnest(lst)))
#[[0], [1], [2, 3, 4], [5, 6], [7], [8, 9]]

Теперь используйте itertools.product, чтобы получить нужную комбинацию элементов: 

from itertools import product
print(list(product(*unnest(lst))))
#[(0, 1, 2, 5, 7, 8),
# (0, 1, 2, 5, 7, 9),
# (0, 1, 2, 6, 7, 8),
# (0, 1, 2, 6, 7, 9),
# (0, 1, 3, 5, 7, 8),
# (0, 1, 3, 5, 7, 9),
# (0, 1, 3, 6, 7, 8),
# (0, 1, 3, 6, 7, 9),
# (0, 1, 4, 5, 7, 8),
# (0, 1, 4, 5, 7, 9),
# (0, 1, 4, 6, 7, 8),
# (0, 1, 4, 6, 7, 9)]

Примечания

  1. yield from работает только в Python 3
0 голосов
/ 29 июня 2019

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

backpointer = {}
rules_prob = {}
syn_tags = []
syn_probs = []

def get_syn_tree(bp, ix):

    if bp[1] - bp[0] == 1:  # end - start = 1   (2, 3, N)
        return

    current_ix = ix
    for i in range(len(backpointer[bp])-1):
        syn_tags.append(syn_tags[current_ix].copy())

    counter = 0
    for item in list(backpointer[bp]):
        # (0, 6, S) -> (4, N,VP) =>     (0, 4, N) , (4, 6, VP)
        syn_tags[current_ix + counter].add((bp[0], item[0], item[1]))
        syn_tags[current_ix + counter].add((item[0], bp[1], item[2]))

        get_syn_tree((bp[0], item[0], item[1]), current_ix + counter)
        get_syn_tree((item[0], bp[1], item[2]), current_ix + counter)

        counter += 1

syn_tags.append({(start, end, A)})
syn_probs.append(0)  # for + = 0, for × = 1
get_syn_tree((start, end, A), 0)
...