元素对的前缀树

Question

我有一个嵌套列表：

lists = [['a', 'b', 'c', 'd'],
         ['a', 'b', 'd', 'e'],
         ['a', 'b', 'd', 'f'],
         ['a', 'b', 'd', 'f', 'h', 'i']]

我知道如何构建一个简单的前缀树：

tree = {}
end = "END"
for lst in lists:
    d = tree
    for x in lst:
        d = d.setdefault(x, {})
    d[end] = {}

结果：

>>> from pprint import pprint
>>> pprint(tree)
{'a': {'b': {'c': {'d': {'END': {}}},
             'd': {'e': {'END': {}},
                   'f': {'END': {}, 'h': {'i': {'END': {}}}}}}}}

现在我可以递归遍历那棵树，每当一个节点只有一个子节点（一个只有一个元素的子字典）时，加入这些节点。

def join(d, pref=[]):
    if end in d:
        yield [' '.join(pref)] if pref else []
    for k, v in d.items():
        if len(v) == 1:
            for x in join(v, pref + [k]): # add node to prefix
                yield x                   # yield next segment
        else:
            for x in join(v, []):         # reset prefix
                yield [' '.join(pref + [k])] + x # yield node + prefix and next

结果：

>>> for x in join(tree):
...     print(x)
...
['a b', 'c d']
['a b', 'd', 'e']
['a b', 'd', 'f']
['a b', 'd', 'f', 'h i']

我需要的是一种算法，其中只有常见的对元素成为树的单个节点。理想情况下，一个节点的最小长度=n1，一个节点的最大长度=n2。期望的输出：

[['a b', 'c d'],
 ['a b', 'd e'],
 ['a b', 'd f'],
 ['a b', 'd f', 'h i']]

Answer 1

只是在加入和屈服之间交替：

def paired(d, _prefix=None):
    if end in d:
        yield [_prefix] if _prefix else []
    for k, v in d.items():
        item = [f'{_prefix} {k}'] if _prefix else []
        for rest in paired(v, None if _prefix else k):
            yield item + rest

因此在每个级别，如果设置了 _prefix，则生成一对，否则离开该级别 'empty' 并以当前密钥作为前缀进行递归。

这会产生您预期的输出：

>>> for path in paired(tree):
...     print(path)
...
['a b', 'c d']
['a b', 'd e']
['a b', 'd f']
['a b', 'd f', 'h i']

元素对的前缀树

Prefix-tree for pairs of elements

python

algorithm

trie

python-3.x