Suppose I have a list of cities :

cities = ['London', 'Berlin', 'Medellín', 'São Paulo', 'Prague', 'Ladakh', 'Nice']

and priority list ( which decides priority between 2 cities):

priorities = [('London', 'Medellín'), ('Medellín', 'São Paulo'), ('Prague', 'Berlin')]

I should be getting output as :

['Nice', 'London', 'Medellín', 'Prague', 'São Paulo', 'Berlin', 'Ladakh']

Example 2:

cities = ['New York', 'Honolulu']
priorities = [('New York', 'Honolulu'), ('Honolulu', 'New York')]
Output: []

since it will contradict the order of each other.

I have not got clear idea how to do this. What i did is to get first all the cities which are not in priority list since it is not dependent and thn create a list of indexed city based on priorities , but where i should go next i am not sure

def get_answer(cities, priorities):
    # get cities not in priorities
    cities_not_in_priorities = [
        city
        for city in cities
        if city not in [city for priority in priorities for city in priority]
    ]
    # get cities in priorities
    cities_in_priorities = [
        city
        for priority in priorities
        for city in priority
        if city not in cities_not_in_priorities
    ]
    print(cities_in_priorities)
    # get cities in priorities with no duplicates
    cities_in_priorities = list(dict.fromkeys(cities_in_priorities))

    print(cities_not_in_priorities)

# create a list of tuples with the index of the city in cities_in_priorities and the city
cities_in_priorities_with_index = [
    (cities_in_priorities.index(city), city)
    for city in cities_in_priorities

]

print(cities_in_priorities_with_index)

CodePudding user response：

Ok so here's my implementation of Kahn's algorithm (thanks David Eisenstat):

cities = ['London', 'Berlin', 'Medellín', 'São Paulo', 'Prague', 'Ladakh', 'Nice']

priorities1 = [('London', 'Medellín'), ('Medellín', 'São Paulo'), ('Prague', 'Berlin')]

priorities2 = [('Berlin', 'Medellin'), ('Medellin', 'Berlin'), ('Ladakh', 'Nice')]


def sort(priorities):
    L = []
    S = []
    for a,b in priorities:
        if a not in [d for c,d in priorities]:
            S.append(a)
            
    while S:
        n = S.pop(0)
        L.append(n)
        for m in [y for x,y in priorities if x==n]:
            priorities.remove((n,m))
            if not [(x,y) for x,y in priorities if y==m]:
                S.append(m)
                
    if priorities:
        return []
    else:
        return L
                
def order(cities, priorities):
    L = sort(priorities)
    if L:
        return L   [c for c in cities if not c in L]
    print("Conflicting priorities")
    return L

Examples:

order(cities, priorities1)
# Out[54]: ['London', 'Prague', 'Medellín', 'Berlin', 'São Paulo', 'Ladakh', 'Nice']

order(cities, priorities2)
# Conflicting priorities
# Out[55]: []

CodePudding user response：

I am unsure how to result in the order to be identical to your example outputs. But, I do have what I believe to be a solution.

cities = ["London", "Berlin", "Medellín", "São Paulo", "Prague", "Ladakh", "Nice"]
priorities = [("London", "Medellín"), ("Medellín", "São Paulo"), ("Prague", "Berlin")]


def solution(cities, priorities):
    res: list[str] = list()
    pq: dict[str, set[str]] = dict()

    # Construct a tree of priorities
    for a, b in priorities:
        if not pq.get(b, None):
            pq[b] = set()
        pq[b].add(a)

        nodes = list([a])
        visited = set([a, b])

        while len(nodes) and (q := pq.get(nodes.pop(), None)):
            for city in q:
                if city in visited:
                    if city == b:  # Detect contradiction
                        return []
                    continue

                pq[b].add(city)
                nodes.append(city)
                visited.add(city)

    for city in cities:
        if not pq.get(city, None) or not res:
            res = [city, *res]
            continue

        for i in reversed(range(0, len(res))):
            if res[i] in pq[city]:
                res = [*res[: i   1], city, *res[i   1 :]]
                break

            if i == 0:
                res.append(city)

    return res


print(solution(cities, priorities))

The resulting output is:

['Nice', 'Ladakh', 'Prague', 'London', 'Medellín', 'São Paulo', 'Berlin']