Python：如何保持具有特定值的列表？

Question

我有如下列表：

myList1

[[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],
 [5, 6, 11, 10],
 [5, 6, 10, 12, 11],
 [6, 11, 12],
 [18, 19, 20, 13],
 [8, 15, 14],
 [8, 14, 15],
 [9, 25, 16],
 [18, 26, 27, 17],
 [13, 17, 19, 26, 27, 28, 18],
 [13, 18, 20, 27, 28, 29, 19],
 [13, 19, 28, 29, 20],
 [30, 21],
 [23, 30, 31, 32, 22],
 [22, 24, 31, 32, 33, 23],
 [23, 32, 33, 34, 24],
 [16, 36, 37, 25],
 [17, 18, 27, 41, 26],
 [17, 18, 19, 26, 28, 41, 42, 27],
 [18, 19, 20, 27, 29, 41, 42, 28],
 [19, 20, 28, 42, 29]]

我想保留包含所有重复值的最长列表

比如我有

[3, 2]
[2, 9, 3]

我想保留[2, 9, 3]

例如，我有：

[6, 10, 11, 5]
[5, 10, 11, 12, 6]

我只想保留[5, 10, 11, 12, 6]

如果我们有

 [17, 18, 27, 41, 26]
 [17, 18, 19, 26, 28, 41, 42, 27]
 [18, 19, 20, 27, 29, 41, 42, 28]

我们应该只有

[17,18, 19, 20, 26,  27, 29, 28, 41, 42]

这就是我所尝试的

def getMaxList(L)
    maxl = dict()
    for vl in L:
        for v in vl:
            maxl[v] = max((maxl.get(v,[]),vl),key=len)  # {value:longest list}
    return [sl for sl in L if sl in map(maxl.get,sl)]

getMaxList(myList1)


[[1, 7, 0],
 [2, 9, 3],
 [4],
 [5, 10, 11, 12, 6],
 [14, 15, 8],
 [13, 17, 19, 26, 27, 28, 18],
 [30, 21],
 [23, 30, 31, 32, 22],
 [22, 24, 31, 32, 33, 23],
 [23, 32, 33, 34, 24],
 [16, 36, 37, 25],
 [17, 18, 19, 26, 28, 41, 42, 27],
 [18, 19, 20, 27, 29, 41, 42, 28]]

Answer 1

在最新更新之后，您现在似乎只希望从所有列表中获得一组唯一的值：

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], [5, 6, 11, 10], [5, 6, 10, 12, 11], [6, 11, 12],
  [18, 19, 20, 13], [8, 15, 14], [8, 14, 15], [9, 25, 16],
  [18, 26, 27, 17], [13, 17, 19, 26, 27, 28, 18],
  [13, 18, 20, 27, 28, 29, 19], [13, 19, 28, 29, 20], [30, 21],
  [23, 30, 31, 32, 22], [22, 24, 31, 32, 33, 23], [23, 32, 33, 34, 24],
  [16, 36, 37, 25], [17, 18, 27, 41, 26], [17, 18, 19, 26, 28, 41, 42, 27],
  [18, 19, 20, 27, 29, 41, 42, 28], [19, 20, 28, 42, 29]]

r = list(set().union(*L))

print(r)    
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 
 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 
 36, 37, 41, 42]

Answer 2

更新

一种有效的方法是使用树状数据结构。它实际上从已排序的列表项遍历并创建尽可能长的分支

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)

[[0, 1, 7], [2, 3, 9], [4], [5, 6, 10, 11, 12], [8, 14, 15], [3, 9, 16]]

---

旧的

不过，我对效率表示怀疑。它已经是O（m*n）。但是你可以试试看

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)

[{4}, 
{9, 2, 3}, 
{0, 1, 7}, 
{8, 14, 15}, 
{16, 9, 3}, 
{5, 6, 10, 11, 12}]