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