Skip to main content

Sort Items by Groups Respecting Dependencies

Question​

Given a list of items with dependencies among them, sort the items such that all items dependent on a particular item are placed after it in the list while preserving the order of the other items.

Example 1
None

Solution​

all//Sort Items by Groups Respecting Dependencies.py


def sort_items_by_groups(items, dependencies):

    sorted_items = []

    # Create a dict to map items to the groups they belong to
    group_map = {}
    for item, group in items:
        group_map[item] = group

    # Create a set of items to track which ones we have already added
    added_items = set()

    # Go through each group and add all the items that don't have any
    # dependencies.
    for group in set(group_map.values()):
        for item in items:
            if item[0] not in added_items and not any([x[0] in added_items and x[1] == item[0] for x in dependencies]):
                sorted_items.append(item)
                added_items.add(item[0])

    # Now go through the dependencies and add the items that have dependencies
    for dependency in dependencies:
        if dependency[0] in added_items and dependency[1] not in added_items:
            for item in items:
                if item[0] == dependency[1]:
                    sorted_items.append(item)
                    added_items.add(item[0])

    return sorted_items