Get number of combinations of nested dictionary with lists

user_9580281 0
Viewed 214

I have a list of nested dictionaries with lists inside and I want to calculate the number of all possible combinations through all the dicts.

Example of input

json = 
[
  {
    "lang": "fr",
    "dates": ["d1", "d2"],
    "address": [
          {
            "city": "Paris",
            "zip": "75001"
          },
          {
            "city": "Lyon",
            "zip": "69600"
          }
          ]
  },
   {
    "lang": "fr",
    "dates": ["d2", "d3"],
    "address": [
          {
            "city": "Paris",
            "zip": "75001"
          }
          ]
  }
]

The expected output would be:

{
 'address.city_dates': {"Paris_d1": 1, "Paris_d2": 2 ,"Paris_d3": 1, "Lyon_d1": 1, "Lyon_d2": 1},
 'address.city_lang': {"Paris_fr": 2, "Lyon_fr": 1},
 'address.city_address.zip': {"Lyon_69600": 1, "Paris_75001": 2},
 'address.zip_dates': {"75001_d1": 1, "75001_d2": 2 ,"75001_d3": 1, "69600_d1": 1, "69600_d2": 1},
 'address.zip_lang': {"75001_fr": 2, "69600_fr": 1}, 
 'dates_lang': {"d1_fr": 1, "d2_fr": ,"d3_fr": 1}
}

Note: Relations are interchangeable in my case: X_Y is similar to Y_X

Attempt: I tried the following function that would be called recursively but I'm stuck at how to deal with lists and look for combinations on all levels.


def get_combs(element, contextKey, relations):
    if type(element) is list:
        # for each element of the list, treat element
        for tokenElement in element:
            get_combs(tokenElement, contextKey, relations)
    elif type(element) is dict:
        keys = list(element.keys())
        keys.sort()
        for first_key in keys:
            # remove current first key to avoid X_Y and Y_X being different
            keys.remove(first_key)
            keys.sort()
            for second_key in keys:
                key = first_key + "_" + second_key
                value_key = str(element[first_key]) + "_" + str(element[second_key])
                if not key in relations:
                    relations[key] = {value_key: 1}
                else:
                    if not value_key in relations[key]:
                        relations[key][value_key] = 1
                    else:
                        relations[key][value_key] += 1
            # recall function to deal wit elements inside the dict
            get_combs(element[first_key], first_key, relations)

def main(json):
    relations = {}
    # loop over all the elements inside json
    for element in json:
        get_combs(element, 'root', relations)
    return relations

pippo = main(json)


print(pippo)

output:

{'address_dates': {"[{'city': 'Paris', 'zip': '75001'}, {'city': 'Lyon', 'zip': '69600'}]_['d1', 'd2']": 1,
                   "[{'city': 'Paris', 'zip': '75001'}]_['d2', 'd3']": 1},
 'address_lang': {"[{'city': 'Paris', 'zip': '75001'}, {'city': 'Lyon', 'zip': '69600'}]_fr": 1,
                  "[{'city': 'Paris', 'zip': '75001'}]_fr": 1},
 'city_zip': {"Lyon_69600": 1, "Paris_75001": 2},
 'lang_dates': {"fr_['d1', 'd2']": 1, "fr_['d2', 'd3']": 1}}
itertools dictionary python
1 Answers

You can recursively flatten the structure, and then group by the formed keys. From there, basic combinations can be applied:

from collections import defaultdict, Counter
import itertools as it
json = [{'lang': 'fr', 'dates': ['d1', 'd2'], 'address': [{'city': 'Paris', 'zip': '75001'}, {'city': 'Lyon', 'zip': '69600'}]}, {'lang': 'fr', 'dates': ['d2', 'd3'], 'address': [{'city': 'Paris', 'zip': '75001'}]}]
def get_keys(d, c = [], j = None):
  if not isinstance(d, (dict, list)):
     yield ('.'.join(c), d, j)
  elif isinstance(d, list):
     yield from [i for j, b in enumerate(d) for i in get_keys(b, c = c, j = j if isinstance(b, dict) else None)]
  else:
     for a, b in d.items():
        yield from get_keys(b, c = c+[a], j = j)
      
def get_combos(data):   
  d = defaultdict(list)
  for a, *b in get_keys(data):
     d[a].append(b)
  return {f'{b}_{a}':Counter([f'{y}_{x}' for [x, l1], [y, l2] in it.product(d[a], d[b]) if type(l1) != type(l2) or l1 == l2]) for a, b in it.combinations(d, 2)}

new_d = {}
for i in json:
   for a, b in get_combos(i).items():
     for c, d in b.items():
        new_d[a] = {**(l:=new_d.get(a, {})), c:d if c not in l else l[c]+d}

Output:

{'dates_lang': {'d1_fr': 1, 'd2_fr': 2, 'd3_fr': 1}, 'address.city_lang': {'Paris_fr': 2, 'Lyon_fr': 1}, 'address.zip_lang': {'75001_fr': 2, '69600_fr': 1}, 'address.city_dates': {'Paris_d1': 1, 'Lyon_d1': 1, 'Paris_d2': 2, 'Lyon_d2': 1, 'Paris_d3': 1}, 'address.zip_dates': {'75001_d1': 1, '69600_d1': 1, '75001_d2': 2, '69600_d2': 1, '75001_d3': 1}, 'address.zip_address.city': {'75001_Paris': 2, '69600_Lyon': 1}}

Edit: to print the flattened structure, store the get_keys call first:

def get_combos(data):   
  d = defaultdict(list)
  t_result = list(get_keys(data))
  print(t_result) #displaying flattened input dict
  for a, *b in t_result:
     d[a].append(b)
  return {f'{b}_{a}':Counter([f'{y}_{x}' for [x, l1], [y, l2] in it.product(d[a], d[b]) if type(l1) != type(l2) or l1 == l2]) for a, b in it.combinations(d, 2)}
user_73267380
Related