Sortieren einer Liste mit Relative Wegangaben

Question

Dies ist eher eine begriffliche Programmierung Frage ist, so mit mir tragen:

Sagen Sie bitte eine Liste von Szenen in einem Film haben, und jede Szene Bezug auf Vergangenheit kann oder auch nicht machen/zukünftige Szenen im selben Film. Ich versuche den effizientesten Algorithmus zum Sortieren dieser Szenen zu finden. Möglicherweise sind nicht genügend Informationen vorhanden, damit die Szenen vollständig sortiert sind.

Hier einige Beispiel-Code in Python (ziemlich Pseudo-Code) zu klären:

class Reference: 
    def __init__(self, scene_id, relation): 
     self.scene_id = scene_id 
     self.relation = relation 


class Scene: 
    def __init__(self, scene_id, references): 
     self.id = scene_id 
     self.references = references 

    def __repr__(self): 
     return self.id 


def relative_sort(scenes): 
    return scenes # Algorithm in question 


def main(): 
    s1 = Scene('s1', [ 
     Reference('s3', 'after') 
    ]) 
    s2 = Scene('s2', [ 
     Reference('s1', 'before'), 
     Reference('s4', 'after') 
    ]) 
    s3 = Scene('s3', [ 
     Reference('s4', 'after') 
    ]) 
    s4 = Scene('s4', [ 
     Reference('s2', 'before') 
    ]) 

    print relative_sort([s1, s2, s3, s4]) 


if __name__ == '__main__': 
    main() 

Das Ziel ist relative_sort Rückkehr [s4, s3, s2, s1] in diesem Fall zu haben.

Wenn es hilfreich ist, kann ich meinen ersten Versuch mit dem Algorithmus teilen; Es ist mir peinlich, wie brutal es ist. Außerdem, wenn Sie sich fragen, ich versuche, die Handlung des Films "Mulholland Drive" zu entschlüsseln.

FYI: Das Python-Tag ist nur hier, weil mein Pseudocode in Python geschrieben wurde.

Answer 1

Der Algorithmus Sie suchen, ist ein topological sort:

Im Bereich der Informatik, eine topologische Sortierung oder topologischen Anordnung eines gerichteten Graphen eine lineare Ordnung seiner Ecken ist, so dass für jede gerichtete Kante uv von Vertex Bis zum Vertex v kommt du vor v in der Reihenfolge. Zum Beispiel können die Scheitelpunkte des Graphen auszuführende Aufgaben darstellen, und die Kanten können Beschränkungen darstellen, dass eine Aufgabe vor einer anderen ausgeführt werden muss; In dieser Anwendung ist eine topologische Reihenfolge nur eine gültige Reihenfolge für die Aufgaben.

Sie können dies berechnen ziemlich leicht eine Grafik-Bibliothek, zum Beispiel, networkx, die topological_sort implementiert. Zunächst importieren wir die Bibliothek und in der Liste alle Beziehungen zwischen den Szenen - das heißt, alle der gerichteten Kanten im Graphen

>>> import networkx as nx 
>>> relations = [ 
    (3, 1), # 1 after 3 
    (2, 1), # 2 before 1 
    (4, 2), # 2 after 4 
    (4, 3), # 3 after 4 
    (4, 2) # 4 before 2 
] 

Wir haben dann einen gerichteten Graphen erstellen:

>>> g = nx.DiGraph(relations) 

Dann laufen wir Eine topologische Sortierung:

Answer 2

Ich habe Ihren modifizierten Code in meine Antwort eingefügt, der das aktuelle (kleine) Problem löst, aber ohne ein größeres Beispielproblem, ich bin nicht sicher, wie gut es skalieren würde. Wenn Sie das eigentliche Problem, das Sie lösen möchten, angeben, würde ich gerne diesen Code testen und verfeinern, bis er an diesem Problem arbeitet, aber ohne Testdaten werde ich diese Lösung nicht weiter optimieren.

Für den Anfang verfolgen wir Verweise als Sätze, nicht als Listen.

• Dubletten wirklich nicht uns helfen (wenn „s1“ vor „s2“ und „s1“ vor „s2“, wir keine Informationen gewonnen haben)
• Auf diese Weise können wir auch inverse Verweise mit Abbruch (wenn "s1" vor "s2" steht, dann kommt "s2" nach "s1").

Wir berechnen eine Min- und Max-Position:

• Min Position auf, wie viele Szenen, die wir kommen nach
• Diese leicht erweitert werden könnte: Wenn wir nach zwei Szenen mit MIN_POS von 2 kommen , unser min_pos ist 4 (Wenn man 2 ist, muss andere 3 sein)
• Max position basierend auf wie viele Dinge wir vor
• Das könnte ähnlich erweitert werden: Wenn wir vor zwei Szenen mit einem max_pos von 4 kommen, Unser max_pos ist 2 (Wenn eins 4 ist, othe r muss 0) sein 3)
• Wenn Sie dies tun, ersetzen Sie einfach pass in tighten_bounds(self) mit Code, um zu versuchen, die Grenzen für eine einzelne Szene zu straffen (und setzen Sie away_updated auf wahr, wenn es funktioniert).

Die Magie ist in get_possible_orders

• alle gültigen Ordnungen generiert, wenn Sie über sie iterieren
• Wenn Sie nur eine gültige Bestellung wollen, ist es nicht die Zeit nehmen, sie alle
zu erstellen

Code:

class Reference: 
    def __init__(self, scene_id, relation): 
     self.scene_id = scene_id 
     self.relation = relation 

    def __repr__(self): 
     return '"%s %s"' % (self.relation, self.scene_id) 

    def __hash__(self): 
     return hash(self.scene_id) 

    def __eq__(self, other): 
     return self.scene_id == other.scene_id and self.relation == other.relation 


class Scene: 
    def __init__(self, title, references): 
     self.title = title 
     self.references = references 
     self.min_pos = 0 
     self.max_pos = None 

    def __repr__(self): 
     return '%s (%s,%s)' % (self.title, self.min_pos, self.max_pos) 

inverse_relation = {'before': 'after', 'after': 'before'} 


def inverted_reference(scene, reference): 
    return Reference(scene.title, inverse_relation[reference.relation]) 


def is_valid_addition(scenes_so_far, new_scene, scenes_to_go): 
    previous_ids = {s.title for s in scenes_so_far} 
    future_ids = {s.title for s in scenes_to_go} 
    for ref in new_scene.references: 
     if ref.relation == 'before' and ref.scene_id in previous_ids: 
      return False 
     elif ref.relation == 'after' and ref.scene_id in future_ids: 
      return False 
    return True 


class Movie: 
    def __init__(self, scene_list): 
     self.num_scenes = len(scene_list) 
     self.scene_dict = {scene.title: scene for scene in scene_list} 
     self.set_max_positions() 
     self.add_inverse_relations() 
     self.bound_min_max_pos() 
     self.can_tighten = True 
     while self.can_tighten: 
      self.tighten_bounds() 

    def set_max_positions(self): 
     for scene in self.scene_dict.values(): 
      scene.max_pos = self.num_scenes - 1 

    def add_inverse_relations(self): 
     for scene in self.scene_dict.values(): 
      for ref in scene.references: 
       self.scene_dict[ref.scene_id].references.add(inverted_reference(scene, ref)) 

    def bound_min_max_pos(self): 
     for scene in self.scene_dict.values(): 
      for ref in scene.references: 
       if ref.relation == 'before': 
        scene.max_pos -= 1 
       elif ref.relation == 'after': 
        scene.min_pos += 1 

    def tighten_bounds(self): 
     anything_updated = False 
     for scene in self.scene_dict.values(): 
      pass 
      # If bounds for any scene are tightened, set anything_updated back to true 
     self.can_tighten = anything_updated 

    def get_possible_orders(self, scenes_so_far): 
     if len(scenes_so_far) == self.num_scenes: 
      yield scenes_so_far 
      raise StopIteration 
     n = len(scenes_so_far) 
     scenes_left = set(self.scene_dict.values()) - set(scenes_so_far) 
     valid_next_scenes = set(s 
           for s in scenes_left 
           if s.min_pos <= n <= s.max_pos) 
     # valid_next_scenes = sorted(valid_next_scenes, key=lambda s: s.min_pos * self.num_scenes + s.max_pos) 
     for s in valid_next_scenes: 
      if is_valid_addition(scenes_so_far, s, scenes_left - {s}): 
       for valid_complete_sequence in self.get_possible_orders(scenes_so_far + (s,)): 
        yield valid_complete_sequence 

    def get_possible_order(self): 
     return self.get_possible_orders(tuple()).__next__() 


def relative_sort(lst): 
    try: 
     return [s.title for s in Movie(lst).get_possible_order()] 
    except StopIteration: 
     return None 


def main(): 
    s1 = Scene('s1', {Reference('s3', 'after')}) 
    s2 = Scene('s2', { 
     Reference('s1', 'before'), 
     Reference('s4', 'after') 
    }) 
    s3 = Scene('s3', { 
     Reference('s4', 'after') 
    }) 
    s4 = Scene('s4', { 
     Reference('s2', 'before') 
    }) 

    print(relative_sort([s1, s2, s3, s4])) 


if __name__ == '__main__': 
    main() 

Answer 3

Wie andere bereits erwähnt haben, brauchen Sie eine topologische Sortierung. Eine Tiefen-Traversierung des gerichteten Graphen, wo die Ordnungsrelation die Kanten bildet, ist alles was Sie brauchen. Besuchen Sie in der Nachbestellung. Dies ist die Umkehrung einer Topo-Sorte. Um die Topo-Sortierung zu erhalten, kehren Sie einfach das Ergebnis um.

Ich habe Ihre Daten als eine Liste von Paaren codiert, die zeigen, was bekannt ist, bevor was geht. Dies ist nur um meinen Code kurz zu halten. Sie können ebenso einfach Ihre Liste von Klassen durchqueren, um das Diagramm zu erstellen.

Beachten Sie, dass die sortierte Menge die Definition eines erfüllen muss, damit topo sortierbar ist. Ihnen geht es gut. Ordnungsbeschränkungen für zeitliche Ereignisse erfüllen natürlich die Definition.

Beachten Sie, dass es durchaus möglich ist, ein Diagramm mit Zyklen zu erstellen. Es gibt keine Topo-Art eines solchen Graphen. Diese Implementierung erkennt keine Zyklen, aber es wäre einfach, sie zu ändern, um dies zu tun.

Natürlich können Sie eine Bibliothek verwenden, um die Topo-Sortierung zu bekommen, aber wo ist der Spaß dabei? Dann

from collections import defaultdict 

# Before -> After pairs dictating order. Repeats are okay. Cycles aren't. 
# This is OP's data in a friendlier form. 
OrderRelation = [('s3','s1'), ('s2','s1'), ('s4','s2'), ('s4','s3'), ('s4','s2')] 

class OrderGraph: 
    # nodes is an optional list of items for use when some aren't related at all 
    def __init__(self, relation, nodes=[]): 
    self.succ = defaultdict(set) # Successor map 
    heads = set() 
    for tail, head in relation: 
     self.succ[tail].add(head) 
     heads.add(head) 
    # Sources are nodes that have no in-edges (tails - heads) 
    self.sources = set(self.succ.keys()) - heads | set(nodes) 

    # Recursive helper to traverse the graph and visit in post order 
    def __traverse(self, start): 
    if start in self.visited: return 
    self.visited.add(start) 
    for succ in self.succ[start]: self.__traverse(succ) 
    self.sorted.append(start) # Append in post-order 

    # Return a reverse post-order visit, which is a topo sort. Not thread safe. 
    def topoSort(self): 
    self.visited = set() 
    self.sorted = [] 
    for source in self.sources: self.__traverse(source) 
    self.sorted.reverse() 
    return self.sorted 

...

>>> print OrderGraph(OrderRelation).topoSort() 
['s4', 's2', 's3', 's1'] 

>>> print OrderGraph(OrderRelation, ['s1', 'unordered']).topoSort() 
['s4', 's2', 's3', 'unordered', 's1'] 

Der zweite Aufruf zeigt, dass Sie gegebenenfalls Werte passieren kann in einer separaten Liste sortiert werden. Sie können, haben aber keine Erwähnung bereits in den Beziehungspaaren.Natürlich können diejenigen, die nicht in den Auftragspaaren aufgeführt sind, überall in der Ausgabe erscheinen.