Блог

Главная - Вопросы по программированию - Как сортировать с помощью логики

Как сортировать с помощью логики

#python

#python

Вопрос:

С четырьмя словарями grandpa , dad , son_1 и son_2 :

 grandpa = {'name': 'grandpa', 'parents': []}
dad = {'name': 'dad', 'parents': ['grandpa']}
son_1 = {'name': 'son_1', 'parents': ['dad']}
son_2 = {'name': 'son_2', 'parents': ['dad']}
relatives = [son_1, grandpa, dad, son_2]

Я хочу написать функцию, которая сортирует всех этих родственников в «обратном» порядке.
Таким образом, вместо parents там будет children использоваться list. Самый старый grandpa был бы на верхнем уровне result словаря, dad был бы ниже со своим children списком, хранящим son_1 и son_2 :

 def sortRelatives(relatives):
    # returns a resulted dictionary:
    # logic


result = sortRelatives(relatives)
print result

Что бы выводило:

 result = {'name': 'grandpa', 
            'children': [
                        {'name': 'dad', 
                        'children': [{'name': 'son_1', 'children': [] },
                                     {'name': 'son_2', 'children': [] }] }
                        ]

        }

Как заставить sortRelatives функцию выполнять такую сортировку?

Комментарии:

1. The oldest grandpa would be on the top level of result dictionary По какому полю вы сортируете? Например, возраст не включен в ваш словарь.

2. @ScottSkiles Тот, у которого пусто 'parents' , я полагаю

3. В этом примере имена уникальны, и существует только один родительский элемент. Разумно ли это предположение, или ваши фактические данные сильно отличаются от того, чем вы поделились здесь?

4. Я думаю, что вопрос нуждается в существенном уточнении… (Однако я не понизил голос)

5. Это не называется сортировкой. Это своего рода поиск или сопоставление. Я не понимаю, почему это должно быть рекурсивным? Откуда взялось это требование? Это домашнее задание?

Ответ №1:

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

 from collections import defaultdict

def children(relatives):
    children = defaultdict(list)
    for person in relatives:
        for parent in person['parents']:
            children[parent].append(person)
    return children

Другой инструмент, который мы можем использовать, — это функция, которая найдет корень нашей генеалогии: 

 def genealogy_root(relatives):
    for person in relatives:
        if not person['parents']:
            return person
    raise TypeError("This doesn't look like a valid genealogy.")

Это поможет нам определить местонахождение человека, у которого нет родителя, и, следовательно, он будет корнем нашего генеалогического дерева. Теперь, когда у нас есть все необходимые инструменты, нам просто нужно создать выходные данные:

 def build_genealogy(relatives):
    relatives_children = children(relatives)

    def sub_genealogy(current_person):
        name = current_person['name']
        return dict(
            name=name,
            children=[sub_genealogy(child) for child in relatives_children[name]] 
        )

    root = genealogy_root(relatives)
    return sub_genealogy(root)

result = build_genealogy(relatives)
print(result)

Какие результаты:

 {
  'name': 'grandpa', 'children': [
     {'name': 'dad', 'children': [
         {'name': 'son_1', 'children': []}, 
         {'name': 'son_2', 'children': []}
     ]}
  ]
}

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

 grandpa = {'name': 'grandpa', 'parents': []}
dad = {'name': 'dad', 'parents': [grandpa]}
son_1 = {'name': 'son_1', 'parents': [dad]}
son_2 = {'name': 'son_2', 'parents': [dad]}
relatives = [grandpa, dad, son_1, son_2]