Qual é a melhor maneira de classificar uma lista parcialmente ordenado?

Question

Provavelmente melhor ilustrado com um pequeno exemplo.
Dadas as relações

A < B < C
A < P < Q 

saídas correto seria

ABCPQ or APQBC or APBCQ ... etc.

Em outras palavras, qualquer ordenação é válida em que as relações dadas segurar.

Estou mais interessado na solução que é mais fácil de implementar, mas o melhor O (n) em velocidade e tempo é interessante também.

Answer 1

Isso é chamado topológica classificação .

O algoritmo padrão é a saída de um elemento mínimo, em seguida, removê-lo e repita até feito.

Answer 2

Faça vários tipos. Primeiro tipo de acordo com a primeira regra, em seguida, de acordo com o segundo e assim por diante. Deve funcionar, a menos que suas regras contêm contradições. Certifique-se bastante fácil de implementar.

Answer 3

Você poderia chamar repetidamente make_heap, pop_heap em C ++ com a seqüência em questão.