How do I merge lists with common elements, where these elements themselves are lists/tuples?

user_9172718 0
Viewed 126

I have this nested list and I need to loop through it in some way to merge inner lists that have common elements (where these elements are lists in themselves). Here is a simplified data that has the pattern of the existing original data:

data = [
        [[0,1],[2,3],[4,5]], 
        [[2,3],[4,5]], 
        [[4,5]], 
        [[6,7],[8,9],[10,11]], 
        [[8,9],[10,11]], 
        [[10,11]], 
        [[12,13],[14,15],[16,17],[18,19],[20,21]], 
        [[14,15],[16,17],[18,19],[20,21]], 
        [[16,17],[18,19],[20,21]],
        [[18,19],[20,21]],
        [[20,21]]
       ]

I want to obtain a merged nested list as given given below:

merged = [
      [[0,1],[2,3],[4,5]], 
      [[6,7],[8,9],[10,11]], 
      [[12,13],[14,15],[16,17],[18,19],[20,21]]
     ]

Below is what I have tried which unfortunately is not going beyong the second inner for loop and is returning the error AttributeError: 'int' object has no attribute 'values':

tmp = {}
for subl in original:
    subl = list(set(subl))                        # Eliminating duplicates by first converting to a set
    subl = dict(zip(subl, range(len(subl))))      # Create dictionary from list
    sublswitch = {y:x for x,y in subl.items()}    # Swap dictionary key for values and vice versa                
    ii = 0
    for key in sublswitch:            
        tmp.setdefault(key.values(), set()).add(list(key.values())[ii])
        ii += 1                                         

out = []
for k, v in tmp.items():
    out.append([[k, i] for i in v])
arraylist set list dictionary python
3 Answers

Here is a solution that uses O(n) additional space which tracks all sub-lists that are already added using a hash table (thus, all lookups would just be O(1)).

added = set()
merged = []

for item in data:
    filtered = list(filter(lambda value: value not in added, map(tuple, item)))
    if filtered:
        added.update(filtered)
        merged.append(list(map(list, filtered)))

print(merged)

Output

[[[0, 1], [2, 3], [4, 5]], [[6, 7], [8, 9], [10, 11]], [[12, 13], [14, 15], [16, 17], [18, 19], [20, 21]]]

Update

The solution above only prevents duplicate list items from occurring again on the next list. Here, we wouldn't only prevent them from occurring again but also merge them on existing ones. As a result, the time complexity of this algorithm is somewhat O(n^2).

merged = []

for item in data:
    item_set = set(map(tuple, item))
    for result in merged:
        if result & item_set:
            result.update(item_set)
            break
    else:
        merged.append(item_set)

merged = [sorted(map(list, item)) for item in merged]
print(merged)
user_110438250

Try this loop:

newdata = []
for lst in data:
    if newdata:
        x = [i for i in lst if i not in newdata[-1]]
        if x:
            newdata.append(x)
    else:
        newdata.append(lst)
print(newdata)

Output:

[[[0, 1], [2, 3], [4, 5]], [[6, 7], [8, 9], [10, 11]], [[12, 13], [14, 15], [16, 17], [18, 19], [20, 21]]]
user_87083640

UPDATED

try this,

def sort_list(data):
    data = sorted(data, key=itemgetter(0))
    return_list = []
    for lst in data:
        new_list = sorted(lst, key=itemgetter(0))
        if not return_list:
            return_list.append(new_list)
            continue
        if new_list[0] not in return_list[-1]:
            return_list.append(new_list)
        if new_list[0] in return_list[-1] and len(new_list) > 
                                                len(return_list[-1]):
            return_list.remove(return_list[-1])
            return_list.append(new_list)
    return return_list

so you can sort the list

data = [[],
    [[0,1],[2,3]],
    [[0,1],[2,3],[4,5]], 
    [[2,3],[4,5]], 
    [[4,5]], 
    [[6,7],[8,9],[10,11]], 
    [[8,9],[10,11]], 
    [[10,11]], 
    [[12,13],[14,15],[16,17],[18,19],[20,21]], 
    [[14,15],[16,17],[18,19],[20,21]], 
    [[16,17],[18,19],[20,21]],
    [[18,19],[20,21]],
    [[20,21]]
   ]

to

[[],
 [[0, 1], [2, 3], [4, 5]],
 [[6, 7], [8, 9], [10, 11]],
 [[12, 13], [14, 15], [16, 17], [18, 19], [20, 21]]]
user_94843310
Related