Print order of people in a dictionary

followers.py

#!/usr/bin/env/python3


def link_map(items):
    res = {}
    for idx, it in enumerate(items):
        if idx == 0:
            continue
        res[items[idx - 1]] = it

    return res


def find_head(links):
    followers = links.values()
    for a in links.keys():
        if a not in followers:
            return a


def sort_people(links):
    res = []
    head = find_head(links)
    _sort_people(res, head, links)
    return res


def _sort_people(res, current, remaining):
    if not remaining:
        return sorted
    else:
        nxt = remaining[current]
        if len(remaining) > 1:
            res.append(current)
            del remaining[current]
            _sort_people(res, nxt, remaining)
        else:
            res.append(current)
            res.append(remaining[current])


if __name__ == "__main__":
    # input data
    raw_people = "xavier robert phil zach bob john toby ash horacio jenkins skip".split(" ")

    # create the people links data structure
    people_links = link_map(raw_people)
    sorted_people = sort_people(people_links)
    assert raw_people == sorted_people

    # manually specify the mapping structure with eyeball randomized order since in Python 3.7 insertion order is
    # guaranteed and the dict created from the link_map call is going to have ordered inserts as the list is traversed
    people2 = {'jenkins': 'skip',
               'ash': 'horacio',
               'bob': 'john',
               'zach': 'bob',
               'john': 'toby',
               'horacio': 'jenkins',
               'phil': 'zach',
               'xavier': 'robert',
               'robert': 'phil',
               'toby': 'ash'}

    sorted_people2 = sort_people(people2)
    # check that the first sort is equal to the second sort
    assert sorted_people == sorted_people2

    print("Original: {}".format(raw_people))
    print("Sorted 1: {}".format(sorted_people))
    print("Sorted 2: {}".format(sorted_people2))