排序與相對位置數據

Question

這更多的是一種概念上的編程問題，如此忍受我的列表：

假設你有一個電影場景的列表，每個場景可能會或可能不會提及過去/未來的場景在同一部電影中。我試圖找到排序這些場景的最有效的算法。當然，可能沒有足夠的信息來完全排序場景。

這裏是用Python一些示例代碼（相當多的僞代碼）澄清：

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() 

我們的目標是在這種情況下relative_sort回報[s4, s3, s2, s1]。

如果有幫助，我可以分享我對算法的初始嘗試;對於它的蠻力，我感到有些尷尬。另外，如果你想知道，我正試圖解碼電影「Mulholland Drive」的情節。

僅供參考：因爲我的僞代碼是用Python編寫的，所以Python代碼只在這裏。

Answer 1

你正在尋找的算法是一個topological sort：

在計算機科學，拓撲排序或有向圖的拓撲排序的領域是其頂點的線性順序，使得從頂點每向邊紫外你到頂點v，你在排序前v。例如，圖的頂點可以表示要執行的任務，並且邊可以表示一個任務必須在另一個之前執行的約束;在這個應用程序中，拓撲排序只是這些任務的有效順序。

您可以使用圖庫很容易地計算出這個值，例如networkx，它實現了topological_sort。首先，我們導入庫並列出所有場景之間的關係 - 即所有在圖中有向邊的

>>> 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 
] 

我們再創建一個有向圖：

>>> g = nx.DiGraph(relations) 

然後我們運行一種拓撲排序：

>>> nx.topological_sort(g) 
[4, 3, 2, 1] 

Answer 2

我已將您的修改後的代碼包含在我的答案中，它解決了當前（小）問題，但沒有更大的示例問題，我不確定它會如何擴展。如果您提供了您正在嘗試解決的實際問題，我很樂意測試並優化該代碼，直到它解決該問題，但是如果沒有測試數據，我不會進一步優化此解決方案。

對於初學者，我們追蹤引用作爲集合，而不是列表。

• 重複沒有真正幫助我們（如「S1」，「S2」面前，「S1」，「S2」之前，我們已經獲得了無信息）
• 這也讓我們補充與反引用放棄（如果「s1」在「s2」之前，那麼「s2」在「s1」之後）。

我們計算最低和最高位置：

• 敏位置，並根據我們
• 這可以很容易地擴展後，有多少場面來了：如果我們來的兩個場景後的2 min_pos ，我們min_pos是4（如果是2，其他必須是3）基於有多少事情我們來
• 之前，這也同樣可以擴展
• 最大的位置是：如果我們來之前的兩個場景爲4 max_pos，我們的max_pos是2（如果一個是4， r必須是3）
• 如果你決定這樣做，只需用代替pass代碼，試圖收緊單個場景的邊界（並且如果它有效，則將anything_updated設置爲true）。

神奇的是在get_possible_orders

• 生成的所有有效排序，如果你遍歷它
• 如果你只想要一個有效的排序，它並不需要創建它們全部
時間

代碼：

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

正如其他人指出的那樣，您需要一種拓撲排序。有序圖形的深度優先遍歷就是您所需要的。以郵購方式訪問。這與拓撲排序相反。所以要得到這個拓撲排序，只需改變結果。

我已將您的數據編碼爲一系列對，顯示之前已知的內容。這只是爲了保持我的代碼簡短。您可以輕鬆遍歷類的列表以創建圖。

請注意，對於拓樸排序有意義，要排序的集合必須滿足partial order的定義。你很好。對時間事件的順序約束自然滿足定義。

注意完全可以創建一個帶週期的圖形。這種圖形沒有topo排序。這個實現不會檢測週期，但修改它會很容易。

當然，您可以使用庫來獲取topo排序，但其中的樂趣在哪裏？

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'] 

第二個呼叫顯示，您可以選擇通過在一個單獨的列表進行排序的值。您可能在關係對中沒有提及值。當然，那些沒有提到的順序對可以隨意出現在輸出的任何地方。