orden de clasificación parcial?

Question

decir que tenemos algunos artículos, y cada uno define unas reglas de clasificación parciales, así:

estoy A y quiero ser antes B

estoy C y yo quiero estar después A pero antes D

Así que tenemos artículos A,B,C,D con estas reglas:

• A>B
• C<A, C>D
• nada más! Por lo tanto, B y D no tienen 'preferencias' en el pedido y se consideran iguales.

Como ve, las reglas de relación transitiva no funcionan aquí. Sin embargo, si A>B todavía significa que B<A. Por lo tanto, no puede haber varios posibles resultados de la clasificación:

1. A B C D
2. A C D B
3. A C B D
4. A B C D

¿Cómo puedo implementar un algoritmo de ordenación que se encarga de esta situación?

---

La razón: hay múltiples módulos de carga dinámica, y algunos de ellos dependen '' a los demás de una manera. Cada módulo puede declarar reglas simples, en relación con otros módulos:

me carga antes de módulo A

a cargar después de módulo B

a cargar antes del módulo A, pero después de módulo B

ahora tengo que poner en práctica este ordenamiento de alguna manera .. :)

---

Respuesta: code por Paddy McCarthy (MIT)

## {{{ http://code.activestate.com/recipes/577413/ (r1) 
try: 
    from functools import reduce 
except: 
    pass 

data = { 
    'des_system_lib': set('std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee'.split()), 
    'dw01':    set('ieee dw01 dware gtech'.split()), 
    'dw02':    set('ieee dw02 dware'.split()), 
    'dw03':    set('std synopsys dware dw03 dw02 dw01 ieee gtech'.split()), 
    'dw04':    set('dw04 ieee dw01 dware gtech'.split()), 
    'dw05':    set('dw05 ieee dware'.split()), 
    'dw06':    set('dw06 ieee dware'.split()), 
    'dw07':    set('ieee dware'.split()), 
    'dware':   set('ieee dware'.split()), 
    'gtech':   set('ieee gtech'.split()), 
    'ramlib':   set('std ieee'.split()), 
    'std_cell_lib':  set('ieee std_cell_lib'.split()), 
    'synopsys':   set(), 
    } 

def toposort2(data): 
    for k, v in data.items(): 
     v.discard(k) # Ignore self dependencies 
    extra_items_in_deps = reduce(set.union, data.values()) - set(data.keys()) 
    data.update({item:set() for item in extra_items_in_deps}) 
    while True: 
     ordered = set(item for item,dep in data.items() if not dep) 
     if not ordered: 
      break 
     yield ' '.join(sorted(ordered)) 
     data = {item: (dep - ordered) for item,dep in data.items() 
       if item not in ordered} 
    assert not data, "A cyclic dependency exists amongst %r" % data 

print ('\n'.join(toposort2(data))) 
## end of http://code.activestate.com/recipes/577413/ }}} 

Answer 1

Usted querrá construir un dependency graph (que es sólo un sabor de grafo dirigido), y luego seguir un orden topologically sorted. Ha pasado un tiempo desde que tomé una clase de combinatoria, por lo que el artículo de Wikipedia probablemente será más útil que lo que soy para un algoritmo de clasificación topológica. Espero que darle la terminología adecuada sea útil. :)

En cuanto a la construcción del gráfico, básicamente solo necesitará tener cada módulo con una lista de las dependencias de ese módulo.

Simplemente tendrá que reformular sus reglas un poco ... "Estoy C y quiero estar después de A, pero antes D" se expresaría como "C depende de A" y "D depende" en C ", de manera que todo fluye en una dirección estándar.