[PYTHON] 공통 요소를 공유하는 목록 병합

공통 요소를 공유하는 목록 병합

내 입력은 목록의 목록입니다. 그들 중 일부는 공통 요소를 공유합니다.

L = [['a','b','c'],['b','d','e'],['k'],['o','p'],['e','f'],['p','a'],['d','g']]

공통된 요소를 공유하는 모든 목록을 병합해야하며 동일한 항목이있는 목록이 더 이상없는 한이 절차를 반복해야합니다. 부울 연산과 while 루프를 사용하는 방법에 대해 생각했지만 좋은 해결책이 없었습니다.

최종 결과는 다음과 같아야합니다.

L = [['a','b','c','d','e','f','g','o','p'],['k']] 

해결법

1. ==============================

   1.그래프의 표기법으로 목록을 볼 수 있습니다. 즉, [ 'a', 'b', 'c']는 서로 연결된 3 개의 노드가있는 그래프입니다. 해결하려는 문제는이 그래프에서 연결된 구성 요소를 찾는 것입니다.

   그래프의 표기법으로 목록을 볼 수 있습니다. 즉, [ 'a', 'b', 'c']는 서로 연결된 3 개의 노드가있는 그래프입니다. 해결하려는 문제는이 그래프에서 연결된 구성 요소를 찾는 것입니다.

   이를 위해 NetworkX를 사용할 수 있습니다. 다음과 같은 이점이 있습니다.

   l = [['a','b','c'],['b','d','e'],['k'],['o','p'],['e','f'],['p','a'],['d','g']]
   
   import networkx 
   from networkx.algorithms.components.connected import connected_components
   
   
   def to_graph(l):
       G = networkx.Graph()
       for part in l:
           # each sublist is a bunch of nodes
           G.add_nodes_from(part)
           # it also imlies a number of edges:
           G.add_edges_from(to_edges(part))
       return G
   
   def to_edges(l):
       """ 
           treat `l` as a Graph and returns it's edges 
           to_edges(['a','b','c','d']) -> [(a,b), (b,c),(c,d)]
       """
       it = iter(l)
       last = next(it)
   
       for current in it:
           yield last, current
           last = current    
   
   G = to_graph(l)
   print connected_components(G)
   # prints [['a', 'c', 'b', 'e', 'd', 'g', 'f', 'o', 'p'], ['k']]
   

   이 문제를 효율적으로 해결하려면 목록을 무언가의 그래프로 변환해야합니다. 따라서 처음부터 networkX를 사용할 수도 있습니다.

2. ==============================

   2.연산:

   연산:

   따라서 목록 대신 집합을 사용하고자 할 수 있습니다. 다음과 같은 프로그램이 그것을해야합니다.

   l = [['a', 'b', 'c'], ['b', 'd', 'e'], ['k'], ['o', 'p'], ['e', 'f'], ['p', 'a'], ['d', 'g']]
   
   out = []
   while len(l)>0:
       first, *rest = l
       first = set(first)
   
       lf = -1
       while len(first)>lf:
           lf = len(first)
   
           rest2 = []
           for r in rest:
               if len(first.intersection(set(r)))>0:
                   first |= set(r)
               else:
                   rest2.append(r)     
           rest = rest2
   
       out.append(first)
       l = rest
   
   print(out)
   

3. ==============================

   3.나는 공통 가치를 가진 목록을 합쳐 내려고하는 것과 같은 문제에 직면했다. 이 예가 귀하가 찾고있는 것일 수 있습니다. 목록을 한 번만 반복하고 결과 집합을 업데이트합니다.

   나는 공통 가치를 가진 목록을 합쳐 내려고하는 것과 같은 문제에 직면했다. 이 예가 귀하가 찾고있는 것일 수 있습니다. 목록을 한 번만 반복하고 결과 집합을 업데이트합니다.

   lists = [['a','b','c'],['b','d','e'],['k'],['o','p'],['e','f'],['p','a'],['d','g']]
   lists = sorted([sorted(x) for x in lists]) #Sorts lists in place so you dont miss things. Trust me, needs to be done.
   
   resultslist = [] #Create the empty result list.
   
   if len(lists) >= 1: # If your list is empty then you dont need to do anything.
       resultlist = [lists[0]] #Add the first item to your resultset
       if len(lists) > 1: #If there is only one list in your list then you dont need to do anything.
           for l in lists[1:]: #Loop through lists starting at list 1
               listset = set(l) #Turn you list into a set
               merged = False #Trigger
               for index in range(len(resultlist)): #Use indexes of the list for speed.
                   rset = set(resultlist[index]) #Get list from you resultset as a set
                   if len(listset & rset) != 0: #If listset and rset have a common value then the len will be greater than 1
                       resultlist[index] = list(listset | rset) #Update the resultlist with the updated union of listset and rset
                       merged = True #Turn trigger to True
                       break #Because you found a match there is no need to continue the for loop.
               if not merged: #If there was no match then add the list to the resultset, so it doesnt get left out.
                   resultlist.append(l)
   print resultlist
   

   resultset = [['a', 'b', 'c', 'd', 'e', 'g', 'f', 'o', 'p'], ['k']]
   

4. ==============================

   4.나는 이것을 문제를 그래프로 모델링함으로써 해결할 수 있다고 생각한다. 각 하위 목록은 노드이며 두 하위 목록에 공통 요소가있는 경우에만 다른 노드와 가장자리를 공유합니다. 따라서 병합 된 하위 목록은 기본적으로 그래프의 연결된 구성 요소입니다. 모두 병합하는 것은 연결된 모든 구성 요소를 찾아서 나열하는 것입니다.

   나는 이것을 문제를 그래프로 모델링함으로써 해결할 수 있다고 생각한다. 각 하위 목록은 노드이며 두 하위 목록에 공통 요소가있는 경우에만 다른 노드와 가장자리를 공유합니다. 따라서 병합 된 하위 목록은 기본적으로 그래프의 연결된 구성 요소입니다. 모두 병합하는 것은 연결된 모든 구성 요소를 찾아서 나열하는 것입니다.

   이는 그래프를 통해 간단한 탐색을 통해 수행 할 수 있습니다. BFS와 DFS 모두 사용할 수 있지만, DFS는 다소 짧습니다.

   l = [['a','b','c'],['b','d','e'],['k'],['o','p'],['e','f'],['p','a'],['d','g']]
   taken=[False]*len(l)
   l=map(set,l)
   
   def dfs(node,index):
       taken[index]=True
       ret=node
       for i,item in enumerate(l):
           if not taken[i] and not ret.isdisjoint(item):
               ret.update(dfs(item,i))
       return ret
   
   def merge_all():
       ret=[]
       for i,node in enumerate(l):
           if not taken[i]:
               ret.append(list(dfs(node,i)))
       return ret
   
   print merge_all()
   

5. ==============================

   5.Jochen Ritzel은 연결된 구성 요소를 그래프로 찾고 있다고 지적했습니다. 그래프 라이브러리를 사용하지 않고 구현할 수있는 방법은 다음과 같습니다.

   Jochen Ritzel은 연결된 구성 요소를 그래프로 찾고 있다고 지적했습니다. 그래프 라이브러리를 사용하지 않고 구현할 수있는 방법은 다음과 같습니다.

   from collections import defaultdict
   
   def connected_components(lists):
       neighbors = defaultdict(set)
       seen = set()
       for each in lists:
           for item in each:
               neighbors[item].update(each)
       def component(node, neighbors=neighbors, seen=seen, see=seen.add):
           nodes = set([node])
           next_node = nodes.pop
           while nodes:
               node = next_node()
               see(node)
               nodes |= neighbors[node] - seen
               yield node
       for node in neighbors:
           if node not in seen:
               yield sorted(component(node))
   
   L = [['a','b','c'],['b','d','e'],['k'],['o','p'],['e','f'],['p','a'],['d','g']]
   print list(connected_components(L))
   

6. ==============================

   6.내 시도. 기능적으로 보입니다.

   내 시도. 기능적으로 보입니다.

   #!/usr/bin/python
   from collections import defaultdict
   l = [['a','b','c'],['b','d','e'],['k'],['o','p'],['e','f'],['p','a'],['d','g']]
   hashdict = defaultdict(int)
   
   def hashit(x, y):
       for i in y: x[i] += 1
       return x
   
   def merge(x, y):
       sums = sum([hashdict[i] for i in y])
       if sums > len(y):
           x[0] = x[0].union(y)
       else:
           x[1] = x[1].union(y)
       return x
   
   
   hashdict = reduce(hashit, l, hashdict)
   sets = reduce(merge, l, [set(),set()])
   print [list(sets[0]), list(sets[1])]
   

7. ==============================

   7.itertools는 목록을 병합하는 빠른 옵션을 찾았고이 문제를 해결했습니다.

   itertools는 목록을 병합하는 빠른 옵션을 찾았고이 문제를 해결했습니다.

   import itertools
   
   LL = set(itertools.chain.from_iterable(L)) 
   # LL is {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'k', 'o', 'p'}
   
   for each in LL:
     components = [x for x in L if each in x]
     for i in components:
       L.remove(i)
     L += [list(set(itertools.chain.from_iterable(components)))]
   
   # then L = [['k'], ['a', 'c', 'b', 'e', 'd', 'g', 'f', 'o', 'p']]
   

   주파수가 가장 큰 요소에서 가장 작은 요소로 LL을 정렬하는 대형 세트의 경우 약간 속도가 빨라질 수 있습니다

8. ==============================

   8.오히려 큰 목록의 경우 OP 수백만 회에 설명 된 클러스터링 기법을 수행 할 필요가 있었으므로 위에 제안 된 방법 중 어느 것이 가장 정확하고 가장 효과적인지 판단하고 싶었습니다.

   오히려 큰 목록의 경우 OP 수백만 회에 설명 된 클러스터링 기법을 수행 할 필요가 있었으므로 위에 제안 된 방법 중 어느 것이 가장 정확하고 가장 효과적인지 판단하고 싶었습니다.

   위의 각 방법에 대해 2 ^ 1에서 2 ^ 10 크기의 입력 목록에 대해 각 입력에 대해 동일한 입력 목록을 사용하여 10 회의 평가판을 실행하고 위에 제안 된 각 알고리즘의 평균 런타임을 밀리 초 단위로 측정했습니다. 결과는 다음과 같습니다.

   이 결과를 통해 올바른 결과를 일관되게 반환하는 방법을 확인할 수있었습니다. @ jochen 's가 가장 빠릅니다. 일관되게 올바른 결과를 반환하지 않는 방법 중 mak의 솔루션에는 입력 요소 (예 : 목록 구성원 목록이 누락 됨)가 모두 포함되지 않는 경우가 많으며 braaksma, cmangla 및 별표의 솔루션이 최대한 병합되지 않을 수도 있습니다 .

   흥미로운 것은 두 개의 가장 빠르고 올바른 알고리즘이 날짜별로 상위 2 개의 양을 가지고 있고 순위가 적절하게 정렬되어 있다는 것입니다.

   다음은 테스트를 실행하는 데 사용되는 코드입니다.

   from networkx.algorithms.components.connected import connected_components
   from itertools import chain
   from random import randint, random
   from collections import defaultdict, deque
   from copy import deepcopy
   from multiprocessing import Pool
   import networkx
   import datetime
   import os
   
   ##
   # @mimomu
   ##
   
   def mimomu(l):
     l = deepcopy(l)
     s = set(chain.from_iterable(l))
     for i in s:
       components = [x for x in l if i in x]
       for j in components:
         l.remove(j)
       l += [list(set(chain.from_iterable(components)))]
     return l
   
   ##
   # @Howard
   ##
   
   def howard(l):
     out = []
     while len(l)>0:
         first, *rest = l
         first = set(first)
   
         lf = -1
         while len(first)>lf:
             lf = len(first)
   
             rest2 = []
             for r in rest:
                 if len(first.intersection(set(r)))>0:
                     first |= set(r)
                 else:
                     rest2.append(r)
             rest = rest2
   
         out.append(first)
         l = rest
     return out
   
   ##
   # Nx @Jochen Ritzel
   ##
   
   def jochen(l):
     l = deepcopy(l)
   
     def to_graph(l):
         G = networkx.Graph()
         for part in l:
             # each sublist is a bunch of nodes
             G.add_nodes_from(part)
             # it also imlies a number of edges:
             G.add_edges_from(to_edges(part))
         return G
   
     def to_edges(l):
         """
             treat `l` as a Graph and returns it's edges
             to_edges(['a','b','c','d']) -> [(a,b), (b,c),(c,d)]
         """
         it = iter(l)
         last = next(it)
   
         for current in it:
             yield last, current
             last = current
   
     G = to_graph(l)
     return list(connected_components(G))
   
   ##
   # Merge all @MAK
   ##
   
   def mak(l):
     l = deepcopy(l)
     taken=[False]*len(l)
     l=map(set,l)
   
     def dfs(node,index):
         taken[index]=True
         ret=node
         for i,item in enumerate(l):
             if not taken[i] and not ret.isdisjoint(item):
                 ret.update(dfs(item,i))
         return ret
   
     def merge_all():
         ret=[]
         for i,node in enumerate(l):
             if not taken[i]:
                 ret.append(list(dfs(node,i)))
         return ret
   
     result = list(merge_all())
     return result
   
   ##
   # @cmangla
   ##
   
   def cmangla(l):
     l = deepcopy(l)
     len_l = len(l)
     i = 0
     while i < (len_l - 1):
       for j in range(i + 1, len_l):
         # i,j iterate over all pairs of l's elements including new
         # elements from merged pairs. We use len_l because len(l)
         # may change as we iterate
         i_set = set(l[i])
         j_set = set(l[j])
   
         if len(i_set.intersection(j_set)) > 0:
           # Remove these two from list
           l.pop(j)
           l.pop(i)
   
           # Merge them and append to the orig. list
           ij_union = list(i_set.union(j_set))
           l.append(ij_union)
   
           # len(l) has changed
           len_l -= 1
   
           # adjust 'i' because elements shifted
           i -= 1
   
           # abort inner loop, continue with next l[i]
           break
   
         i += 1
     return l
   
   ##
   # @pillmuncher
   ##
   
   def pillmuncher(l):
     l = deepcopy(l)
   
     def connected_components(lists):
       neighbors = defaultdict(set)
       seen = set()
       for each in lists:
           for item in each:
               neighbors[item].update(each)
       def component(node, neighbors=neighbors, seen=seen, see=seen.add):
           nodes = set([node])
           next_node = nodes.pop
           while nodes:
               node = next_node()
               see(node)
               nodes |= neighbors[node] - seen
               yield node
       for node in neighbors:
           if node not in seen:
               yield sorted(component(node))
   
     return list(connected_components(l))
   
   ##
   # @NicholasBraaksma
   ##
   
   def braaksma(l):
     l = deepcopy(l)
     lists = sorted([sorted(x) for x in l]) #Sorts lists in place so you dont miss things. Trust me, needs to be done.
   
     resultslist = [] #Create the empty result list.
   
     if len(lists) >= 1: # If your list is empty then you dont need to do anything.
         resultlist = [lists[0]] #Add the first item to your resultset
         if len(lists) > 1: #If there is only one list in your list then you dont need to do anything.
             for l in lists[1:]: #Loop through lists starting at list 1
                 listset = set(l) #Turn you list into a set
                 merged = False #Trigger
                 for index in range(len(resultlist)): #Use indexes of the list for speed.
                     rset = set(resultlist[index]) #Get list from you resultset as a set
                     if len(listset & rset) != 0: #If listset and rset have a common value then the len will be greater than 1
                         resultlist[index] = list(listset | rset) #Update the resultlist with the updated union of listset and rset
                         merged = True #Turn trigger to True
                         break #Because you found a match there is no need to continue the for loop.
                 if not merged: #If there was no match then add the list to the resultset, so it doesnt get left out.
                     resultlist.append(l)
     return resultlist
   
   ##
   # @Rumple Stiltskin
   ##
   
   def stiltskin(l):
     l = deepcopy(l)
     hashdict = defaultdict(int)
   
     def hashit(x, y):
         for i in y: x[i] += 1
         return x
   
     def merge(x, y):
         sums = sum([hashdict[i] for i in y])
         if sums > len(y):
             x[0] = x[0].union(y)
         else:
             x[1] = x[1].union(y)
         return x
   
     hashdict = reduce(hashit, l, hashdict)
     sets = reduce(merge, l, [set(),set()])
     return list(sets)
   
   ##
   # @Asterisk
   ##
   
   def asterisk(l):
     l = deepcopy(l)
     results = {}
     for sm in ['min', 'max']:
       sort_method = min if sm == 'min' else max
       l = sorted(l, key=lambda x:sort_method(x))
       queue = deque(l)
   
       grouped = []
       while len(queue) >= 2:
         l1 = queue.popleft()
         l2 = queue.popleft()
         s1 = set(l1)
         s2 = set(l2)
   
         if s1 & s2:
           queue.appendleft(s1 | s2)
         else:
           grouped.append(s1)
           queue.appendleft(s2)
       if queue:
         grouped.append(queue.pop())
       results[sm] = grouped
     if len(results['min']) < len(results['max']):
       return results['min']
     return results['max']
   
   ##
   # Validate no more clusters can be merged
   ##
   
   def validate(output, L):
     # validate all sublists are maximally merged
     d = defaultdict(list)
     for idx, i in enumerate(output):
       for j in i:
         d[j].append(i)
     if any([len(i) > 1 for i in d.values()]):
       return 'not maximally merged'
     # validate all items in L are accounted for
     all_items = set(chain.from_iterable(L))
     accounted_items = set(chain.from_iterable(output))
     if all_items != accounted_items:
       return 'missing items'
     # validate results are good
     return 'true'
   
   ##
   # Timers
   ##
   
   def time(func, L):
     start = datetime.datetime.now()
     result = func(L)
     delta = datetime.datetime.now() - start
     return result, delta
   
   ##
   # Function runner
   ##
   
   def run_func(args):
     func, L, input_size = args
     results, elapsed = time(func, L)
     validation_result = validate(results, L)
     return func.__name__, input_size, elapsed, validation_result
   
   ##
   # Main
   ##
   
   all_results = defaultdict(lambda: defaultdict(list))
   funcs = [mimomu, howard, jochen, mak, cmangla, braaksma, asterisk]
   args = []
   
   for trial in range(10):
     for s in range(10):
       input_size = 2**s
   
       # get some random inputs to use for all trials at this size
       L = []
       for i in range(input_size):
         sublist = []
         for j in range(randint(5, 10)):
           sublist.append(randint(0, 2**24))
         L.append(sublist)
       for i in funcs:
         args.append([i, L, input_size])
   
   pool = Pool()
   for result in pool.imap(run_func, args):
     func_name, input_size, elapsed, validation_result = result
     all_results[func_name][input_size].append({
       'time': elapsed,
       'validation': validation_result,
     })
     # show the running time for the function at this input size
     print(input_size, func_name, elapsed, validation_result)
   pool.close()
   pool.join()
   
   # write the average of time trials at each size for each function
   with open('times.tsv', 'w') as out:
     for func in all_results:
       validations = [i['validation'] for j in all_results[func] for i in all_results[func][j]]
       linetype = 'incorrect results' if any([i != 'true' for i in validations]) else 'correct results'
   
       for input_size in all_results[func]:
         all_times = [i['time'].microseconds for i in all_results[func][input_size]]
         avg_time = sum(all_times) / len(all_times)
   
         out.write(func + '\t' + str(input_size) + '\t' + \
           str(avg_time) + '\t' + linetype + '\n')
   

   그리고 음모를 꾸미기 위해 :

   library(ggplot2)
   df <- read.table('times.tsv', sep='\t')
   
   p <- ggplot(df, aes(x=V2, y=V3, color=as.factor(V1))) +
     geom_line() +
     xlab('number of input lists') +
     ylab('runtime (ms)') +
     labs(color='') +
     scale_x_continuous(trans='log10') +
     facet_wrap(~V4, ncol=1)
   
   ggsave('runtimes.png')
   

9. ==============================

   9.당신이 원하는 것을 모르는 사이에 나는 당신이 의미하는 바를 추측하기로 결정했습니다. 나는 모든 요소를 ​​단 한번만 찾고 싶습니다.

   당신이 원하는 것을 모르는 사이에 나는 당신이 의미하는 바를 추측하기로 결정했습니다. 나는 모든 요소를 ​​단 한번만 찾고 싶습니다.

   #!/usr/bin/python
   
   
   def clink(l, acc):
     for sub in l:
       if sub.__class__ == list:
         clink(sub, acc)
       else:
         acc[sub]=1
   
   def clunk(l):
     acc = {}
     clink(l, acc)
     print acc.keys()
   
   l = [['a', 'b', 'c'], ['b', 'd', 'e'], ['k'], ['o', 'p'], ['e', 'f'], ['p', 'a'], ['d', 'g']]
   
   clunk(l)
   

   출력은 다음과 같습니다.

   ['a', 'c', 'b', 'e', 'd', 'g', 'f', 'k', 'o', 'p']
   

10. ==============================

    10.이것은 아마도 더 간단하거나 빠른 알고리즘 일 것이며 잘 작동하는 것 같습니다.

    이것은 아마도 더 간단하거나 빠른 알고리즘 일 것이며 잘 작동하는 것 같습니다.

    l = [['a', 'b', 'c'], ['b', 'd', 'e'], ['k'], ['o', 'p'], ['e', 'f'], ['p', 'a'], ['d', 'g']]
    
    len_l = len(l)
    i = 0
    while i < (len_l - 1):
        for j in range(i + 1, len_l):
    
            # i,j iterate over all pairs of l's elements including new 
            # elements from merged pairs. We use len_l because len(l)
            # may change as we iterate
            i_set = set(l[i])
            j_set = set(l[j])
    
            if len(i_set.intersection(j_set)) > 0:
                # Remove these two from list
                l.pop(j)
                l.pop(i)
    
                # Merge them and append to the orig. list
                ij_union = list(i_set.union(j_set))
                l.append(ij_union)
    
                # len(l) has changed
                len_l -= 1
    
                # adjust 'i' because elements shifted
                i -= 1
    
                # abort inner loop, continue with next l[i]
                break
    
        i += 1
    
    print l
    # prints [['k'], ['a', 'c', 'b', 'e', 'd', 'g', 'f', 'o', 'p']]
    

11. ==============================

    11.이것은 의존성이없는 상당히 빠른 솔루션입니다. 그것은 다음과 같이 작동합니다 :

    이것은 의존성이없는 상당히 빠른 솔루션입니다. 그것은 다음과 같이 작동합니다 :

    이 절차에서 변경 사항이 발생하지 않으면 모든 요소가 정확히 하나의 목록에 포함되어 있기 때문입니다. 작업 집합은 매 반복마다 크기가 감소하므로 알고리즘은 반드시 종료됩니다.

       def merge_overlapping_sublists(lst):
        output, refs = {}, {}
        for index, sublist in enumerate(lst):
            output[index] = set(sublist)
            for elem in sublist:
                refs[elem] = index
        changes = True
        while changes:
            changes = False
            for ref_num, sublist in list(output.items()):
                for elem in sublist:
                    current_ref_num = refs[elem]
                    if current_ref_num != ref_num:
                        changes = True
                        output[current_ref_num] |= sublist
                        for elem2 in sublist:
                            refs[elem2] = current_ref_num
                        output.pop(ref_num)
                        break
        return list(output.values())
    

    다음은이 코드에 대한 일련의 테스트입니다.

    def compare(a, b):
        a = list(b)
        try:
            for elem in a:
                b.remove(elem)
        except ValueError:
            return False
        return not b
    
    import random
    lst = [["a", "b"], ["b", "c"], ["c", "d"], ["d", "e"]]
    random.shuffle(lst)
    assert compare(merge_overlapping_sublists(lst), [{"a", "b", "c", "d", "e"}])
    lst = [["a", "b"], ["b", "c"], ["f", "d"], ["d", "e"]]
    random.shuffle(lst)
    assert compare(merge_overlapping_sublists(lst), [{"a", "b", "c",}, {"d", "e", "f"}])
    lst = [["a", "b"], ["k", "c"], ["f", "g"], ["d", "e"]]
    random.shuffle(lst)
    assert compare(merge_overlapping_sublists(lst), [{"a", "b"}, {"k", "c"}, {"f", "g"}, {"d", "e"}])
    lst = [["a", "b", "c"], ["b", "d", "e"], ["k"], ["o", "p"], ["e", "f"], ["p", "a"], ["d", "g"]]
    random.shuffle(lst)
    assert compare(merge_overlapping_sublists(lst), [{"k"}, {"a", "c", "b", "e", "d", "g", "f", "o", "p"}])    
    lst = [["a", "b"], ["b", "c"], ["a"], ["a"], ["b"]]
    random.shuffle(lst)
    assert compare(merge_overlapping_sublists(lst), [{"a", "b", "c"}])
    

    반환 값은 집합의 목록입니다.

from https://stackoverflow.com/questions/4842613/merge-lists-that-share-common-elements by cc-by-sa and MIT license