擅长:python、mysql、java
<p>您可以通过两个步骤完成此操作:首先,构建元组的<a href="https://en.wikipedia.org/wiki/Trie" rel="nofollow noreferrer">Trie</a>或前缀树:</p>
<pre><code>tuples = set([(), (1,), (1,1), (1,2), (2,), (2,1,1), (2,1,2), (2,2)])
tree = {}
for tpl in tuples:
t = tree
for x in tpl:
t = t.setdefault(x, {})
</code></pre>
<p>在您的示例中,<code>tree</code>将是<code>{1: {1: {}, 2: {}}, 2: {1: {1: {}, 2: {}}, 2: {}}}</code></p>
<p>然后,只要当前元组(树中的路径)在<code>set</code>(为了更快地查找)的<code>tuples</code>中,DFS就会进入树并向组添加元素。(树中的叶子始终是有效的元组。)</p>
<pre><code>def find_groups(tree, path):
if len(tree) == 0:
yield [path]
for x in tree:
for res in find_groups(tree[x], path + (x,)):
yield [path] + res if path in tuples else res
</code></pre>
<p>这将产生:</p>
<pre><code>[(), (1,), (1, 1)]
[(), (1,), (1, 2)]
[(), (2,), (2, 1, 1)]
[(), (2,), (2, 1, 2)]
[(), (2,), (2, 2)]
</code></pre>
<p>复杂性应该是O(k),k是所有元组中元素的总和,即树中中间节点和叶节点的总数。你知道吗</p>