0

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 example:

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

group_dict(dictionary)

would give back:

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

UPDATE

The "real" structure of the dictionary is:

dictionary = {'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'}, 'group3' :{'IDs': ['h','z'], 'oldest_node': 'node_9'}

I want to generate the most inclusive groups and keep the lowest value of the node variable:

dictionary = {'group1' :{'IDs': ['a','b','c','d','e'], 'oldest_node': 'node_30'}, 'group3' :{'IDs': ['h','k','z','w','x','j'], 'oldest_node': 'node_2'}}
biojl
  • 1,060
  • 1
  • 8
  • 26

2 Answers2

2

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


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

    while True:
        dest = {}
        count = 0
        while src:
            k1, temp = src.popitem()
            if temp is None:
                continue
            for k2, v in src.iteritems():
                if v is None:
                    continue
                if 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


def print_dict(d):
    for k in sorted(d.keys()):
        print "%s: %s" % (k, d[k])
    print


def main():
    print_dict(groups)
    print 20*'-'

    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'},
}


def merge_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)

    while True:
        dest = {}
        count = 0
        while src:
            k1, temp = src.popitem()
            if temp is None:
                continue
            for k2, v in src.iteritems():
                if v is None:
                    continue
                if temp['IDs'] & v['IDs']:
                    #Merge IDs
                    temp['IDs'] |= v['IDs']

                    #Determine key of merge from oldest_node
                    if 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:
            break
        else:
            #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


def print_dict(d):
    for k in sorted(d.keys()):
        print "%s: %s" % (k, d[k])
    print


def main():
    print_dict(groups)
    print 20*'-'

    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'}
PM 2Ring
  • 54,345
  • 6
  • 82
  • 182
1

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.

cezar
  • 11,616
  • 6
  • 48
  • 84
  • It doesn't matter, I can generate a new dictionary. Removing the duplicates will be a little bit more complicated because I have to decide which copy to keep based on the value of another variable in the dictionary. Is there an easy way to retrieve all the keys with the same values? I would easily decide based on the other variable in the dict. – biojl Nov 17 '14 at 13:16
  • I don't know any built-in that finds duplicate values in a dictionary. You could try with ``d.get(k1) in d1.values()``, where ``d`` is the dictionary and ``k1`` the key. It`ll get the value for ``k1`` and check if it is already in the dictionary ``d1``. You can prior to this copy the dictionary ``d`` to ``d1`` and make ``d1.remove(k1)``. – cezar Nov 17 '14 at 13:39
  • What would happen with a case like @user3684792 proposes (how would a case group 5 : ['g', 'a'] affect things?). In your code it will be absorbed by group3 or group1 but won't combine them all in a single group, am I right? – biojl Nov 17 '14 at 13:55
  • When I wrote the example I didn't consider the case with 'group5'. It'll mess the things definitely. Your assumption is right. It'll put together 'group1', 'group2' and 'group5', but will omit 'group3' and 'group4', where it should actually merge all groups together. The main problem with dictionaries is the issue with only one possible key. Maybe you can generate some intermediate list or tuple and in the end generate the needed dictionary. But it wouldn't be very simple. – cezar Nov 17 '14 at 14:04
  • @biojl: The above code can only merge pairs of items, so it doesn't handle more complex relationships between multiple items. You can run it through multiple cycles to improve merging, though that makes it O(n^3), which will be slow for big dicts. – PM 2Ring Nov 17 '14 at 14:06
  • Yes, I thought of recursively run it... but it's proven to be very slow. The dictionary is very big and it's been running for almost an hour now (first run). – biojl Nov 17 '14 at 14:20
  • @biojl: There are a few quick improvements you can make to cezars code that would improve speed. Eg, Scan through the dict converting all lists to sets before you start merging. And you can eliminate dupes by using a set (let's call it `pool`) that holds a copy of the new values created by the union operation. Only add a new value to `result` (and to `pool`) if it's not already in `pool`. – PM 2Ring Nov 17 '14 at 14:31
  • @PM2Ring I already eliminated dupes using set for every key before running it. About the second part I don't quite understand it – biojl Nov 17 '14 at 14:41