CODEWITHSUNDEEP
pythonpython-3.xrecursion
User
User

Reputation: 95

Recursively combine dictionaries

Alright, this is doing my head in. I have two dictionaries with object groups as shown below:

groups = {
    'servers': ['unix_servers', 'windows_servers'],
    'unix_servers': ['server_a', 'server_b', 'server_group'],
    'windows_servers': ['server_c', 'server_d'],
    'server_group': ['server_e', 'server_f']
}

hosts = {
    'server_a': '10.0.0.1',
    'server_b': '10.0.0.2',
    'server_c': '10.0.0.3',
    'server_d': '10.0.0.4',
    'server_e': '10.0.0.5',
    'server_f': '10.0.0.6'
}

The output I'm looking for is:

d3 = {
    'servers': {
        'unix_servers': {
            'server_a': '10.0.0.1',
            'server_b': '10.0.0.2',
            'server_group': {
                'server_e': '10.0.0.5',
                'server_f': '10.0.0.6'
            }
        },
        'windows_servers': {
            'server_c': '10.0.0.3',
            'server_d': '10.0.0.4'
        }
    }
}

The problem I'm having is that I don't know beforehand how much levels of recursion there are, as nested groups can theoretically go on infinitely. Additionally, I'm having trouble with determining which keys should be a top-level key in the combined dictionary.

I currently have the following:

def resolve(d1, d2):
for k, v in d1.items():
    for i in v:
        if i in d2.keys():
            d3[k] = {i: d2[i]}

This returns:

{
  "servers": {
    "unix_servers": {
      "server_a": "10.0.0.1",
      "server_b": "10.0.0.2",
      "server_group": {
        "server_e": "10.0.0.5",
        "server_f": "10.0.0.6"
      }
    },
    "windows_servers": {
      "server_c": "10.0.0.3",
      "server_d": "10.0.0.4"
    }
  },
  "unix_servers": {
    "server_b": "10.0.0.2"
  },
  "windows_servers": {
    "server_d": "10.0.0.4"
  },
  "server_group": {
    "server_f": "10.0.0.6"
  }
}

Which is close, but it's clearly missing recursion and doesn't handle nesting of keys. Mainly looking for pointers here, recursion logic doesn't click for me yet...

Upvotes: 7

Views: 254

Answers (6)

Shoyeb Sheikh
Shoyeb Sheikh

Reputation: 2866

New to python I have been struggling though this but found a solution at last, it is quite long though.

groups = {
    'servers': ['unix_servers', 'windows_servers'],
    'unix_servers': ['server_a', 'server_b', 'server_group'],
    'windows_servers': ['server_c', 'server_d'],
    'server_group': ['server_e', 'server_f']
}

hosts = {
    'server_a': '10.0.0.1',
    'server_b': '10.0.0.2',
    'server_c': '10.0.0.3',
    'server_d': '10.0.0.4',
    'server_e': '10.0.0.5',
    'server_f': '10.0.0.6'
}

result = {}

parent = '';

levels = [];

def check(s,r):
    if(r[s]==''): #check for each blank element in the result recursively
        sublist = {}
        for k in groups[s]: # check if the key exist in group if exist append children to result.   
            if k in hosts :
                sublist[k] = hosts[k] # check if host exist in hosts for this key
            else:
                sublist[k]=''
        if(key_exist(result, s)): # check if the key exist in result if exist append to result.             
            d = result 
            p = None
            for key in levels:
                p = d
                d = d[key]
            p[key] = sublist
            del levels[:]
        for x in sublist :
            if(sublist[x] == ''):
                check(x,p[key])

def resolve(r):
    for s in r:
        if(isinstance(r[s],dict)):
            return resolve(r[s])
        else:
            check(s,r)


def key_exist(groups, key): 
    for s in groups:
        if key in groups:
            levels.append(key);
            return True
        else:
            if(isinstance(groups[s],dict)):
                levels.append(s);
                return key_exist(groups[s], key)
    return False

# Find the root or parent element
for k in groups.keys(): 
    found = False
    for j in groups.keys(): 
        if k in groups[j]:
            found = False
        else:
            found = True
    if(found):
        parent = k  # root or parent element

# start making result with root element 
s = {}
for k in groups[parent]:
    s[k]='' # initialize child elements with blank
result[parent] = s 

resolve(result) 

print(result)

Upvotes: 0

Ajax1234
Ajax1234

Reputation: 71461

You can use simple recursion:

def build(val): 
  return {i:build(i) for i in groups[val]} if val in groups else hosts[val]

import json
print(json.dumps({'servers':build('servers')}, indent=4))

Output:

{
  "servers": {
    "unix_servers": {
        "server_a": "10.0.0.1",
        "server_b": "10.0.0.2",
        "server_group": {
            "server_e": "10.0.0.5",
            "server_f": "10.0.0.6"
        }
    },
    "windows_servers": {
        "server_c": "10.0.0.3",
        "server_d": "10.0.0.4"
     }
  }
}

Upvotes: 1

Lie Ryan
Lie Ryan

Reputation: 64855

Assuming you're ok with possibly having cross referencing data structure, you don't necessarily need to use recursion here. 

from itertools import chain

group_dicts = {k: {} for k in groups}

for g in group_dicts:
    for child_key in groups[g]:
        child = group_dicts.get(child_key, hosts.get(child_key))
        group_dicts[g][child_key] = child

# remove entries that are referenced at least once
not_top_levels = set(chain.from_iterable(groups.values()))
result = {g: group_dicts[g] for g in group_dicts if g not in not_top_levels}

Unlike other solutions, this will correctly handle cycles and infinitely recursive groups, as all the dict references are shared. When your groups topologically describes a tree, this will work exactly the same as the recursive solution. However, if your groups topologically describes a directed acyclic graph, this solution would share the dicts for all the nodes that appears more than once, while the recursive solution would copy and expand the duplicates out into a regular tree, this wouldn't really be an issue if you don't need to mutate the dicts. If your groups topologically describes a graph with cycles, then this will create those cycles, while the recursive solution would fall due to infinite recursion.

Upvotes: 1

iamv
iamv

Reputation: 51

I guess it needs just two loops, and no more. Here, the groups dict will be updated, more precisely, it'll lose some of its key-values.

groups = {k: {s: None for s in subs} for k, subs in groups.items()}                                                                                                                                                        

for k, subs in groups.items():                                                                                                                                                                                        
    for subs_k, subs_v in subs.items():                                                                                                                                                                                       
        if subs_v is not None:                                                                                                                                                                                         
            continue                                                                                                                                                                                               
        if subs_k in groups:                                                                                                                                                                                           
            groups[k][subs_k] = groups[subs_k]                                                                                                                                                                             
            del groups[subs_k]                                                                                                                                                                                       
        else:                                                                                                                                                                                                      
            groups[k][subs_k] = hosts[subs_k]


print(groups)

you'd probably like to re-write it using defaultdict

Upvotes: 0

Soorya J
Soorya J

Reputation: 23

d3={}
main={}
for i in groups['servers']:
    if(i in groups):
        d={}
        for j in groups[i]:
            if(j in groups):
                dd={}
                for k in groups[j]:
                    dd[k]=hosts[k]
                d[j]=dd
            else:
                d[j]=hosts[j]
        main[i]=d
d3['servers']=main
print(d3)

this will give :

{
    'servers': 
    {
        'unix_servers': 
        {
            'server_group': 
            {
                'server_f': '10.0.0.6', 
                'server_e': '10.0.0.5'
            }, 
            'server_b': '10.0.0.2',
            'server_a': '10.0.0.1'
        }, 
        'windows_servers': 
        {
            'server_c': '10.0.0.3', 
            'server_d': '10.0.0.4'
        }
    }
}

Upvotes: 0

javidcf
javidcf

Reputation: 59711

I think this does what you want:

def resolve(groups, hosts):
    # Groups that have already been resolved
    resolved_groups = {}
    # Group names that are not root
    non_root = set()
    # Make dict with resolution of each group
    result = {}
    for name in groups:
        result[name] = _resolve_rec(name, groups, hosts, resolved_groups, non_root)
    # Remove groups that are not root
    for name in groups:
        if name in non_root:
            del result[name]
    return result

def _resolve_rec(name, groups, hosts, resolved_groups, non_root):
    # If group has already been resolved finish
    if name in resolved_groups:
        return resolved_groups[name]
    # If it is a host finish
    if name in hosts:
        return hosts[name]
    # New group resolution
    resolved = {}
    for child in groups[name]:
        # Resolve each child
        resolved[child] = _resolve_rec(child, groups, hosts, resolved_groups, non_root)
        # Mark child as non-root
        non_root.add(child)
    # Save to resolved groups
    resolved_groups[name] = resolved
    return resolved

With your example:

groups = {
    'servers': ['unix_servers', 'windows_servers'],
    'unix_servers': ['server_a', 'server_b', 'server_group'],
    'windows_servers': ['server_c', 'server_d'],
    'server_group': ['server_e', 'server_f']
}

hosts = {
    'server_a': '10.0.0.1',
    'server_b': '10.0.0.2',
    'server_c': '10.0.0.3',
    'server_d': '10.0.0.4',
    'server_e': '10.0.0.5',
    'server_f': '10.0.0.6'
}

d3 = {
    'servers': {
        'unix_servers': {
            'server_a': '10.0.0.1',
            'server_b': '10.0.0.2',
            'server_group': {
                'server_e': '10.0.0.5',
                'server_f': '10.0.0.6'
            }
        },
        'windows_servers': {
            'server_c': '10.0.0.3',
            'server_d': '10.0.0.4'
        }
    }
}


print(resolve(groups, hosts) == d3)
# True

Note this can fall into infinite recursion for malformed inputs, if you have for example group A containing group B but then group B contains group A.

Upvotes: 3

Related Questions