<p><strong>更新</strong></p>
<p>一种有效的方法是使用树状数据结构。它实际上从已排序的列表项遍历并创建尽可能长的分支</p>
<pre class="lang-py prettyprint-override"><code>l = [[1, 7, 0],[0, 7, 1],[3, 2],[2, 9, 3],[4],[6, 10, 11, 5],[5, 10, 11,12, 6],[0, 1, 7],[14, 15, 8],[3, 16, 9]]
class Node:
def __init__(self, value):
self.value = value
self.children = []
class Tree:
def __init__(self):
self.root = Node(-1)
def add_a_list(self, l):
l = sorted(l)
pin = None
for each_child in self.root.children:
if(l[0] == each_child.value):
pin = each_child
break
if(pin == None):
self.add_as_a_new_branch(l)
else:
self.add_with_existing_pin(pin, l[1:])
def add_with_existing_pin(self, pin, l):
if(len(l) == 0):
return
for each_child in pin.children:
if(each_child.value == l[0]):
self.add_with_existing_pin(each_child, l[1:])
return
sc = Node(l[0])
pin.children.append(sc)
if(len(l) == 1):
return
current = sc
for i in l[1:]:
tt = Node(i)
current.children.append(tt)
current = tt
def add_as_a_new_branch(self, l):
rt = Node(l[0])
self.root.children.append(rt)
if(len(l) == 1):
return
current = rt
for i in l[1:]:
tt = Node(i)
current.children.append(tt)
current = tt
def gb(self):
output = []
self.generate_branches(self.root, output, [])
return output
def generate_branches(self, r, output, prev):
for each_child in r.children:
each_child.till_now = prev
#print(each_child.value, prev, [i.value for i in each_child.children])
if(len(each_child.children) == 0):
output.append([*each_child.till_now, each_child.value])
else:
self.generate_branches(each_child, output, [*each_child.till_now, each_child.value])
t = Tree()
for i in l:
t.add_a_list(i)
result = t.gb()
print(result)
</code></pre>
<pre><code>[[0, 1, 7], [2, 3, 9], [4], [5, 6, 10, 11, 12], [8, 14, 15], [3, 9, 16]]
</code></pre>
<hr/>
<p><strong>旧的</strong></p>
<p>不过,我对效率表示怀疑。它已经是O(m*n)。但是你可以试试看</p>
<pre class="lang-py prettyprint-override"><code>l = [[1, 7, 0],[0, 7, 1],[3, 2],[2, 9, 3],[4],[6, 10, 11, 5],[5, 10, 11,12, 6],[0, 1, 7],[14, 15, 8],[3, 16, 9]]
l = sorted(l, key=lambda x: len(x)) # sorting to make sure supersets are on right hand side
output = [set(l[0])] # setting the first list element as first element of output
for i in l[1:]:
# this variable will keep track if i is not a superset
# of any of the output elements
not_a_single_super_set = True
for index, j in enumerate(output):
if(set(i).issuperset(j)):
output[index] = set(i)
not_a_single_super_set = False
break
if(not_a_single_super_set):
output.append(set(i))
print(output)
</code></pre>
<pre><code>[{4},
{9, 2, 3},
{0, 1, 7},
{8, 14, 15},
{16, 9, 3},
{5, 6, 10, 11, 12}]
</code></pre>