Удалите ключи из вложенного словаря, если они появляются в другом месте как значение

Question

У меня есть вложенный словарь, содержащий родителей (ключи) и их детей (значения). Я хочу удалить родителей и их дочерние элементы, если родительский элемент является дочерним по отношению к другому родительскому элементу в дереве, т. Е. Я хочу удалить ключ, если он появляется в другом месте в словаре в качестве значения. Вот пример ввода / вывода:

Введите:

{
    "Animal":  {
        "Cat":  [],  
        "Dog":  {
            "Labrador":  {
                "LabradorPup":  []
            }
        }
    },  
    "DieselCar":  {
        "Hyundai":  []
    },  
    "Dog":  {
        "Labrador":  {
            "LabradorPup":  []
        }
    },  
    "ElectricCar":  {
        "Tesla":  []
    },  
    "Labrador":  {
        "LabradorPup":  []
    },  
    "PetrolCar":  {
        "Ford":  [],  
        "Hyundai":  []
    },  
    "Vehicle":  {
        "DieselCar":  {
            "Hyundai":  []
        },  
        "ElectricCar":  {
            "Tesla":  []
        },  
        "PetrolCar":  {
            "Ford":  [],  
            "Hyundai":  []
        }
    }
}

Желаемый вывод:

{
    "Animal":  {
        "Cat":  [],  
        "Dog":  {
            "Labrador":  {
                "LabradorPup":  []
            }
        }
    },  
    "Vehicle":  {
        "DieselCar":  {
            "Hyundai":  []
        },  
        "ElectricCar":  {
            "Tesla":  []
        },  
        "PetrolCar":  {
            "Ford":  [],  
            "Hyundai":  []
        }
    }
}

У меня есть следующий код, который хранит родителей, у которых есть дети, однако это не приводит к выводу, который я ищу:

inheritance_tree = {parent:children for parent, children in inheritance_tree.items() if any(child for child in children.values())}

Вы видите, что клавиша "Dog" не удалена, даже если она является дочерней по отношению к "Animal":

{
    "Animal":  {
        "Cat":  [],  
        "Dog":  {
            "Labrador":  {
                "LabradorPup":  []
            }
        }
    },  
    "Dog":  {
        "Labrador":  {
            "LabradorPup":  []
        }
    },  
    "Vehicle":  {
        "DieselCar":  {
            "Hyundai":  []
        },  
        "ElectricCar":  {
            "Tesla":  []
        },  
        "PetrolCar":  {
            "Ford":  [],  
            "Hyundai":  []
        }
    }
}

Answer 1

inheritance_tree = {
parent:children for parent, children in inheritance_tree.items() if any(
    child for child in children.values()
    )
}

Любые проверки, есть ли у детей собственные дети. То, что делает ваш текущий код, это только родители, у которых есть внуки. Если вы хотите удалить этих детей из списка, вы можете написать функцию, которая просматривает список и изменяет его копию.

Если вы хотите придерживаться одной строки, вам нужно искать родителя в значениях дерева наследования. Однако эти значения могут отличаться от dict, поэтому вам также необходимо проверить это.

y= {parent:children for parent, children in x.items() if all(
[(parent not in set(k.keys())) for k in x.values() if k])
}

Answer 2

Я не думаю, что any(child for child in children.values()) - это эффективный способ определения того, должен ли children оставаться в окончательном положении.Это выражение в основном эквивалентно «имеет ли этот dict хотя бы одно значение, которое не является пустой строкой?».У диктанта Пса непустой ребенок, поэтому он остается в вашем последнем дикте.

Вот подход, который я бы использовал.Напишите функцию, которая рекурсивно перебирает вложенную структуру данных и выдает все ее ключи, независимо от того, насколько глубоко они вложены.Запустите эту функцию для каждой пары ключ-значение верхнего уровня, чтобы определить имена всех дочерних значений.Затем создайте новый dict, исключающий эти имена из верхнего уровня.

def iter_all_keys(obj):
    if not isinstance(obj, dict):
        return
    for key, value in obj.items():
        yield key
        for x in iter_all_keys(value):
            yield x

d = {
    "Animal":  {
        "Cat":  [],  
        "Dog":  {
            "Labrador":  {
                "LabradorPup":  []
            }
        }
    },  
    "DieselCar":  {
        "Hyundai":  []
    },  
    "Dog":  {
        "Labrador":  {
            "LabradorPup":  []
        }
    },  
    "ElectricCar":  {
        "Tesla":  []
    },  
    "Labrador":  {
        "LabradorPup":  []
    },  
    "PetrolCar":  {
        "Ford":  [],  
        "Hyundai":  []
    },  
    "Vehicle":  {
        "DieselCar":  {
            "Hyundai":  []
        },  
        "ElectricCar":  {
            "Tesla":  []
        },  
        "PetrolCar":  {
            "Ford":  [],  
            "Hyundai":  []
        }
    }
}

child_names = {child_name for toplevel_name, toplevel_children in d.items() for child_name in iter_all_keys(toplevel_children)}

d = {key: value for key, value in d.items() if key not in child_names}
print(d)

Результат (пробел, добавленный мной для ясности):

{
    'Animal': {
        'Dog': {
            'Labrador': {
                'LabradorPup': []
            }
        }, 
        'Cat': []
    }, 
    'Vehicle': {
        'DieselCar': {
            'Hyundai': []
        }, 
        'PetrolCar': {
            'Hyundai': [], 
            'Ford': []
        }, 
        'ElectricCar': {
            'Tesla': []
        }
    }
}

Обратите внимание, что при этом удаляются только дубликаты изверхний уровень.Если бы вы запустили этот код в словаре, таком как этот:

d = {
    "Human":{
        "Fred": [],
        "Barney": []
    },
    "Caveman":{
        "Fred": [],
        "Barney": []
    }
}

... Тогда полученный dict будет идентичен вводу.Фред и Барни появляются дважды в структуре данных.Если это не желаемый результат, неясно, каким должен быть результат .Следует ли удалить Фреда и Барни из Человека или из пещерного человека?Если логика должна заключаться в том, чтобы «держать Фреда и Барни в человеке, потому что это та, с которой мы столкнулись первыми. Избавьтесь от всего остального», то результат не будет детерминированным, поскольку словари в 2.7 не гарантированно упорядочены.

Answer 3

Попробуйте:

Я знаю, что это сложно.

aa = [i for i,j in a.items()]
bb = [get_all_keys(j) for i,j in a.items()]

for i in aa:
    for j in bb:
        if i in j:
            for k in a:
                if k==i:
                    del a[k]

Скажи мне, что ты все делаешь правильно или неправильно.