Combine Dictionary Entries By Common Elements

I have a very big dictionary with keys containing a list of items. I would like to group all the keys that have at least one element in the list in common in an efficient way. For

Solution 1:

The program below solves the original problem. There may be a more efficient algorithm, but I think this one is reasonably fast.

It shouldn't be too hard to modify this code to cope with the more complex dict in the updated version of the problem.

(I'm using Python 2.6, so I don't have dict comprehensions, which is why I'm building dicts using generator expressions).

merge_lists.py

#! /usr/bin/env python''' Merge lists in a dict 

    Lists are merged if they have any element in common,
    so that in the resulting dict no list element will be 
    associated with more than one key.

    Written by PM 2Ring 2014.11.18

    From http://stackoverflow.com/q/26972204/4014959
'''#Some test data
groups = {
    'g01': ['a', 'b', 'c', 'd'], 
    'g02': ['a', 'b', 'c', 'd', 'e'], 
    'g03': ['f', 'g', 'h'], 
    'g04': ['g', 'j'],
    #'g05': ['g', 'a'],'g06': ['k', 'l'],
    'g07': ['l', 'm'],
    'g08': ['m', 'n'],
    'g09': ['o', 'p'],
    'g10': ['p', 'q'],
    'g11': ['q', 'o'],
    #'g12': ['l', 'q'],
}


defmerge_lists(d):
    src = dict((k, set(v)) for k, v in d.iteritems())

    whileTrue:
        dest = {}
        count = 0while src:
            k1, temp = src.popitem()
            if temp isNone:
                continuefor k2, v in src.iteritems():
                if v isNone:
                    continueif temp & v:
                    temp |= v
                    src[k2] = None
                    count += 1
                    k1 = min(k1, k2)
            dest[k1] = temp

        if count > 0:
            #print count#print_dict(dest)
            src = dest
        else:
            dest = dict((k, sorted(list(v))) for k, v in dest.iteritems())
            return dest


defprint_dict(d):
    for k insorted(d.keys()):
        print"%s: %s" % (k, d[k])
    printdefmain():
    print_dict(groups)
    print20*'-'

    dest = merge_lists(groups)
    print_dict(dest)


if __name__ == '__main__':  
    main()

output

g02: ['a', 'b', 'c', 'd', 'e']
g03: ['f', 'g', 'h']
g04: ['g', 'j']
g06: ['k', 'l']
g07: ['l', 'm']
g08: ['m', 'n']
g09: ['o', 'p']
g10: ['p', 'q']
g11: ['q', 'o']

--------------------
g01: ['a', 'b', 'c', 'd', 'e']
g03: ['f', 'g', 'h', 'j']
g06: ['k', 'l', 'm', 'n']
g09: ['o', 'p', 'q']

---

Here's a version that works on the updated dict structure.

#! /usr/bin/env python''' Merge lists in a dict 

    Lists are merged if they have any element in common,
    so that in the resulting dict no list element will be 
    associated with more than one key.

    The key of the merged item is selected from the sub-dict with the lowest
    value of oldest_node.

    Written by PM 2Ring 2014.11.21

    From http://stackoverflow.com/q/26972204/4014959
'''#Some test data

groups = {
    'group1': {'IDs': ['a','b','c','d'], 'oldest_node': 'node_30'}, 
    'group2': {'IDs': ['c','d','e'], 'oldest_node': 'node_40'}, 
    'group3': {'IDs': ['h','k'], 'oldest_node': 'node_2'}, 
    'group4': {'IDs': ['z','w','x','j'], 'oldest_node': 'node_6'}, 
    'group5': {'IDs': ['h','z'], 'oldest_node': 'node_9'},
}


defmerge_lists(d):
    #Convert IDs to a set and oldest_node to an int 
    src = {}
    for k, v in d.iteritems():
        src[k] = {
            'IDs': set(v['IDs']), 
            'oldest_node': int(v['oldest_node'][5:])
        } 
    #print_dict(src)whileTrue:
        dest = {}
        count = 0while src:
            k1, temp = src.popitem()
            if temp isNone:
                continuefor k2, v in src.iteritems():
                if v isNone:
                    continueif temp['IDs'] & v['IDs']:
                    #Merge IDs
                    temp['IDs'] |= v['IDs']

                    #Determine key of merge from oldest_nodeif v['oldest_node'] < temp['oldest_node']:
                        k1 = k2
                        temp['oldest_node'] = v['oldest_node']
                    src[k2] = None
                    count += 1
            dest[k1] = temp

        src = dest

        #Exit loop if no changes occured if count == 0:
            breakelse:
            #print count#print_dict(src)pass#Convert dict back to original form
    dest = {}
    for k, v in src.iteritems():
        dest[k] = {
            'IDs': sorted(list(v['IDs'])), 
            'oldest_node': 'node_%d' % v['oldest_node']
        }
    return dest


defprint_dict(d):
    for k insorted(d.keys()):
        print"%s: %s" % (k, d[k])
    printdefmain():
    print_dict(groups)
    print20*'-'

    dest = merge_lists(groups)
    print_dict(dest)


if __name__ == '__main__':  
    main()

output

group1: {'IDs': ['a', 'b', 'c', 'd'], 'oldest_node': 'node_30'}
group2: {'IDs': ['c', 'd', 'e'], 'oldest_node': 'node_40'}
group3: {'IDs': ['h', 'k'], 'oldest_node': 'node_2'}
group4: {'IDs': ['z', 'w', 'x', 'j'], 'oldest_node': 'node_6'}
group5: {'IDs': ['h', 'z'], 'oldest_node': 'node_9'}

--------------------
group1: {'IDs': ['a', 'b', 'c', 'd', 'e'], 'oldest_node': 'node_30'}
group3: {'IDs': ['h', 'j', 'k', 'w', 'x', 'z'], 'oldest_node': 'node_2'}

Solution 2:

Do you really want to change the dictionary that is used as input or is it okay if your function outputs another dictionary as a result?

Here is a quick and dirty function, that groups the values:

def group_dict(d):
    result = {}
    for k1 in d:
        for k2 in d:
            if k1 != k2 and set(d.get(k1)).intersection(d.get(k2)):
                result[k1] = list(set(d.get(k1)).union(d.get(k2)))
    return result

It should return:

{'group1': ['a', 'c', 'b', 'e', 'd'],
 'group2': ['a', 'c', 'b', 'e', 'd'],
 'group3': ['h', 'z', 'g', 'f'],
 'group4': ['h', 'z', 'g', 'f']}

Expand the function to remove the duplicates.

I'm using the built-in set and its methods intersection and union. That should be the key for your core requirements. In a double for-loop (very ugly) the values in the dictionary get compared and if intersection is found, the union of the values is converted to list and assigned to the result dictionary. It's really not a nice solution, but maybe it can give you some idea.