Expanding dict value using keys in the same dictionary-CodePudding

I try to expand the values of a dictionary using keys in the same dictionary. In other words, I try to replace dic values (existing set with another/ potentially expanded set). The expansion happens when the value contains a key in the dictionary.

Input:

dic = {
    '10': {'01', '02'},
    '11': {'03', '04'},
    '20': {'05', '10'},
    '21': {'06', '11'},
    '30': {'07', '20'},
    '40': {'08', '21', '30'},
    '50': {'09', '40'}
}

Expected output:

{
    '10': {'01', '02'},
    '11': {'03', '04'},
    '20': {'05', '01', '02'},
    '21': {'06', '03', '04'},
    '30': {'07', '05', '01', '02'},
    '40': {'08', '06', '03', '04', '07', '05', '01', '02'},
    '50': {'09', '08', '06', '03', '04', '07', '05', '01', '02'}
}

I was trying to create a recursive function...

def transform_dic(d):
    def func(k):
        v = d.get(k, k)
        if v != k:
            for e in v:
                v = func(v)
        return v
    d2 = {}
    for k, v in d.items():
        d2[k] = {func(i) for i in v}
    return d2

print(transform_dic(dic))

TypeError: unhashable type: 'set'

CodePudding user response：

The things that you want to expand recursively are the sets in the dict, not the dict itself. You always only have one dict.

For this reason, I believe it's easier to write a recursive function to expand a set, and then use this function to expand the dict.

def expanded_dict(d):
    return {k: expanded_set(v, d) for k,v in d.items()}

def expanded_set(s, d):
    return {
        y
        for x in s
            for y in (expanded_set(d[x], d) if x in d
                      else (x,))
    }

Note that expanded_set returns a new set without modifying the input set nor the input dict; and expanded_dict returns a new dict without modifying the input dict.

It's good practice to make it clear whether your function returns a new object, or modifies the input object. For instance, sorted returns a new list without modifying its input, whereas list.sort modifies a list without returning anything.

Here is a function which expands a dict by modifying it without returning anything:

def expand_dict(d):
    stable = False
    while not stable:
        stable = True
        for k in d:
            for x in list(d[k]):
                if x in d:
                    d[k].remove(x)
                    d[k].update(d[x])
                    stable = False

Testing with your examples:

dic = {
    '10': {'01', '02'},
    '11': {'03', '04'},
    '20': {'05', '10'},
    '21': {'06', '11'},
    '30': {'07', '20'},
    '40': {'08', '21', '30'},
    '50': {'09', '40'}
}

print(expanded_dict(dic))
# {'10': {'01', '02'}, '11': {'03', '04'}, '20': {'01', '05', '02'}, '21': {'03', '06', '04'}, '30': {'07', '01', '02', '05'}, '40': {'04', '06', '08', '05', '02', '01', '07', '03'}, '50': {'04', '06', '08', '02', '05', '01', '07', '09', '03'}}

print(dic)
# {'10': {'01', '02'}, '11': {'03', '04'}, '20': {'10', '05'}, '21': {'11', '06'}, '30': {'07', '20'}, '40': {'08', '30', '21'}, '50': {'40', '09'}}

expand_dict(dic)
# no return value

print(dic)
# {'10': {'01', '02'}, '11': {'03', '04'}, '20': {'01', '02', '05'}, '21': {'03', '06', '04'}, '30': {'01', '05', '07', '02'}, '40': {'04', '06', '08', '05', '02', '01', '07', '03'}, '50': {'04', '06', '08', '05', '02', '01', '07', '09', '03'}}

CodePudding user response：

You can iterate over output dict and check if values inside the set is member of result dict or not:

from typing import Dict, Set


dic = {
    '10': {'01', '02'},
    '11': {'03', '04'},
    '20': {'05', '10'},
    '21': {'06', '11'},
    '30': {'07', '20'},
    '40': {'08', '21', '30'},
    '50': {'09', '40'}
}

output = {
    '10': {'01', '02'},
    '11': {'03', '04'},
    '20': {'05', '01', '02'},
    '21': {'06', '03', '04'},
    '30': {'07', '05', '01', '02'},
    '40': {'08', '06', '03', '04', '07', '05', '01', '02'},
    '50': {'09', '08', '06', '03', '04', '07', '05', '01', '02'}
}

def conv(d: Dict[str, set[str]]) -> Dict[str, set[str]]:        
    result: Dict[str, set[str]] = {}
    for k,vs in d.items():
        result[k] = set()
        for v in vs:
            if v in result:
                for t in result[v]:
                    result[k].add(t)
            else:
                result[k].add(v)
    return result

print(conv(dic))
print(conv(dic)==output)

the output will be

{'10': {'02', '01'}, '11': {'03', '04'}, '20': {'02', '05', '01'}, '21': {'06', '03', '04'}, '30': {'02', '05', '07', '01'}, '40': {'05', '03', '02', '01', '06', '07', '08', '04'}, '50': {'05', '03', '09', '02', '01', '06', '07', '08', '04'}}
True

CodePudding user response：

Does it have to be recursive?

def transform_dic(d):
    for k, v in d.items():
        for n in set(v):
            if n in d:
                d[k].remove(n)
                d[k].update(d[n])

transform_dic(dic)
print(dic)

If you don't want to modify the original dictionary use deepcopy

def transform_dic(d):
    d = deepcopy(d)
    for k, v in d.items():
        for n in set(v):
            if n in d:
                d[k].remove(n)
                d[k].update(d[n])
    return d

print(transform_dic(dic))

Output:

{
    '10': {'01', '02'},
    '11': {'03', '04'},
    '20': {'01', '05', '02'},
    '21': {'03', '04', '06'},
    '30': {'01', '07', '05', '02'},
    '40': {'01', '08', '07', '04', '06', '03', '05', '02'},
    '50': {'01', '08', '07', '04', '06', '03', '05', '02', '09'}
}