Python: how to keep lists with specific values?

Question

I have list of lists like the following:

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

I want to keep the longest lists that contains all the repeated values.

For instance I have

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

I want to keep [2, 9, 3].

For instance I have:

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

I want to keep only [5, 10, 11, 12, 6].

If we have

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

we should have only

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

This what I tried.

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

After the latest update, you now seem to only want a set of unique values out of all the lists:

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

Update

An efficient way can be use of Tree-like data structure. It actually traverses and creates the longest possible branch from the sorted list items.

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

---

OLD

I am skeptical about the efficiency though. It is already O(m*n). But you can give it a try

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