Início / coding / Perguntas / 79587366
Accepted
rasputin
Asked: 2025-04-23 04:03:04 +0800 CST

Algoritmo eficiente para criar união ordenada de listas com ordenação verdadeira desconhecida

  • 772

Tenho várias listas que preciso combinar. Cada uma dessas listas tem uma ordem, e cada ordem é consistente com a ordem da lista original. (Por consistente, quero dizer que cada lista pode ser reproduzida removendo itens da lista original, sem reorganizar nenhum item .)

Meu problema é que não tenho a lista original e tenho que reproduzi-la o mais fielmente possível usando as listas parciais que tenho.

Por exemplo, considere as seguintes listas ordenadas:

a = ["first", "fourth", "fifth", "sixth", "eighth", "sophomore", "junior"]
b = ["second", "third", "fourth", "sixth", "seventh", "eighth", "freshman", "sophomore", "senior"]
c = ["first", "second", "freshman", "sophomore", "junior", "senior"]
...
partial_lists = [a, b, c, ...]

A partir dessas três listas, é possível recuperar a lista original. Em alguns casos, porém, isso pode não ser possível. De qualquer forma, quero criar uma lista merged_listque merged_listpreserve a ordem de cada uma das listas parciais. (Ou seja, qualquer lista parcial especificada poderia, teoricamente, ser reconstruída merged_listusando apenas merged_list.remove()operações.) É seguro assumir que cada lista parcial não contém duplicatas e merged_listtambém não deve conter nenhuma duplicata.

Para este exemplo, merged_listseria["first", "second", "third", "fourth", "fifth", "sixth", "seventh", "eighth", "freshman", "sophomore", "junior", "senior"]

Existe um algoritmo eficiente que pode lidar com isso para um número arbitrário de listas parciais?

algorithm

1 respostas

  1. Best Answer

    Isto é sobre classificação topológica , dadas algumas dependências.

    Existem várias maneiras de encontrar uma lista original ordenada topológica. Será útil construir uma estrutura de dados de grafo que tenha todas as dependências codificadas por nós. Em seguida, produza os nós que não têm predecessores e remova-os do grafo. Isso resultará em um novo conjunto de nós sem predecessores, etc.

    Aqui está uma implementação em Python:

    from collections import defaultdict

def topological_sort(lists):
    # create graph (pred + succ)
    succ = defaultdict(set)
    pred = defaultdict(set)
    nodes = set()
    for lst in lists:
        nodes.update(lst)
        for a, b in zip(lst, lst[1:]):
            succ[a].add(b)
            pred[b].add(a)
        
    # get nodes that don't have a predecessor
    first = { node for node in nodes if not pred[node] }

    while first:
        collect = list(first)
        first.clear()
        yield from collect  # yield the nodes that don't have a predecessor (anymore)
        for a in collect:
            for b in succ[a]:
                pred[b].remove(a) # those can't be a predecessor anymore
                if not pred[b]: # this may make another node to be without predecessor
                    first.add(b)
    
        
# demo run:
a = ["first", "fourth", "fifth", "sixth", "eighth", "sophomore", "junior"]
b = ["second", "third", "fourth", "sixth", "seventh", "eighth", "freshman", "sophomore", "senior"]
c = ["first", "second", "freshman", "sophomore", "junior", "senior"]
partial_lists = [a, b, c]
result = list(topological_sort(partial_lists))

    Para este exemplo de execução, o resultresultado será:

    ['first', 'second', 'third', 'fourth', 'fifth', 'sixth', 'seventh', 'eighth', 'freshman', 'sophomore', 'junior', 'senior']
    • 3

relate perguntas