Python的排序基於2類屬性

Question

編輯：剛剛發現我用py 2.6.2（安裝工作，所以我不能做太多的事情）

所以我想找到最好的根據2種不同類別屬性對列表進行排序的方法

此列表基本上是一些信息，用於將某些人從一個房間移動到另一個房間，某些人可能是鏈條移動的一部分 （即Joe Blow必須先移動我們可以將Jane Doe轉移到Joe的位置，Jane必須在John Wick進入Jane的位置之前移動等）。

我得到所有信息somet像下面那樣興奮，但也可能有一些人不像Dan Man在下面的例子中那樣移動鏈條的一部分。

John Wick 303.10 -> 415.09 
Dan Man 409.08 -> 221.02 
Joe Blow 225.06 -> 512.01 
Jane Doe 415.09 -> 225.06 

我把所有的相關信息分成一類

startRoom 
endRoom 
originalString 

所以這部分是不是一個問題，但是當我嘗試「蠻力」之類的像如下：（注意，我做的列表（鏈），因爲它是前面一組，以確保我沒有在那裏獲得雙打）

def sortChains(): 
    global chains 
    #convert the set of chains to a list for list functions 

    chains = list(chains) 
    for x, move1 in enumerate(chains): 
     for y, move2 in enumerate(chains): 
      if move1.startRoom == move2.endRoom: 
       temp = chains[y] 
       chains.remove(move2) 
       chains.insert(x,temp) 
       continue 

我的問題是排序。問題的一個部分是找到鏈中的人，然後在那之後正確排序。 任何想法/幫助是完全讚賞。是的，我知道一個雙循環，而在循環中移動東西並不是最好的，但這是我當時能想到的最好的。

Answer 1

首先，您必須創建一個依賴關係圖並確定（a）哪個人必須移動before其他人可以移動，以及（b）哪些人現在可以移動。我們可以在這裏使用1：1映射，但在更一般的情況下，您可能必須使用1：n，n：1或n：m映射。現在

moves = {"John Wick": ("303.10", "415.09"), 
     "Dan Man": ("409.08", "221.02"), 
     "Joe Blow": ("225.06", "512.01"), 
     "Jane Doe": ("415.09", "225.06")} 
# or dict((move.originalString, (move.startRoom, move.endRoom)) for move in list_of_moves) 

# mapping {initial room -> name} 
rooms = {start: name for (name, (start, end)) in moves.items()} 
# Python 2.6: dict((start, name) for (name, (start, end)) in moves.items()) 

# mapping {moves_first: moves_after} 
before = {rooms[end]: name for name, (start, end) in moves.items() if end in rooms} 
# Python 2.6: dict((rooms[end], name) for name, (start, end) in moves.items() if end in rooms) 

# persons that can move now 
can_move = set(moves) - set(before.values()) 

，我們可以看到誰可以移動，移動的那個人，然後更新誰可以移動基於什麼人不得不等待的人，如果任何移動的人。

result = [] 
while can_move: 
    # get person that can move, add to result 
    name = can_move.pop() 
    result.append(name) 
    # add next to can_move set 
    if name in before: 
     can_move.add(before.pop(name)) 

之後，result是['Joe Blow', 'Jane Doe', 'John Wick', 'Dan Man']

複雜度應該是O（n）的，但當然，這會如果有循環依賴失敗。

Answer 2

def do(moves): 
    """RETURNS: [0] Sequence of persons to move. 
       [1] Remainder 
    """ 
    # (following line copied from 'tobias_k', replaced 'rooms' with 'current_db') 
    # map: target position to person who occupies it 
    current_db = { start: name for (name, (start, end)) in moves.items() } 
    # maintain set of persons who are free to move to their target location 
    liberated_set = set() 
    # map occupier of a location -> set of people who would take his place. 
    liberation_db = defaultdict(set) 
    # whosoever wants to move to a free place -> liberated. 
    # else         -> liberation_db 
    for name, (start, end) in moves.items(): 
     occupier = current_db.get(start) 
     if occupier is None: liberated_set.add(name) 
     else:    liberation_db[occupier].add(name) 

    sequence = [] 
    while liberated_set: 
     # add people to the sequence who are free to move 
     sequence.extend(liberated_set) 
     # get new set of people who are free to move to their target 
     # because their target position is no longer occupied. 
     new_liberated_set = set() 
     for occupier in liberated_set: 
      if not occupier in liberation_db: continue 
      new_liberated_set.extend(liberation_db[occupier]) 
      del liberation_db[occupier] 
     liberated_set = new_liberated_set 

    return sequence, set(liberation_db.values())