元素对的前缀树

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，则生成一对，否则将该级别“空”并以当前键作为前缀进行递归。

这将产生您的预期输出：

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