與拓撲

Question

分組我道歉，如果這個問題已在回答： Topological Sort with Grouping

不過，我不完全理解的答案，因爲我是新來的圖論。

我有以下項目：

c01,a11,b12,a21, b22,c23, c31,b32, a33. 

每一項都是一個三元組。

Tup[0]： '信集團通過'

Tup[1]： '組數，其中依賴性是有效的'

Tup[2]： '的排序順序依賴'

我想組由tup[0]作爲儘可能接近，同時保持item[1]和item[2]中各組描述的排序順序。項目1,2允許我們創建依賴項，從這裏我們只需創建組。

，所以我們可以創建以下depencies：

A11 < -B 12

A21 < -b22，B22 < -c23

C31 < -b32，B32 < -a33

c01

從這裏我想通過信件whi保持依賴關係。一個這樣的解決方案將是

a11, a21, b12, b22, c01, c23, c31, b32, a33 

我們可以看到，A11 < -B 12，A21 < -b22 < -c23，C31 < -b32 < -a33，C01

任何想法，將不勝感激， 謝謝， 羅布

一個解決辦法：

def groupPreserveSorted(listOfPairs): 
    """ 

    we want to group by tup[0], but maintain the order passed in according to tup[1] 

    >>> lop = [['A',0], ['B',1], ['C',0], ['D',2], ['E',2]] 
    >>> print groupPreserveSorted(lop) 
    [('A', 0), ('B', 1), ('C', 0), ('D', 2), ('E', 2)] 

    >>> lop = [['c',0], ['a',1], ['b',1], ['a',2], ['b',2], ['a', 3], ['b', 3], ['c', 3], ['a', 4], ['b', 4]] 
    >>> print groupPreserveSorted(lop) 
    [('c', 0), ('a', 1), ('a', 2), ('a', 3), ('a', 4), ('b', 1), ('b', 2), ('b', 3), ('b', 4), ('c', 3)] 

    >>> lop = [['c',0], ['a',1], ['b',1], ['a',2], ['b',2], ['a', 3], ['b', 3], ['c', 3], ['c', 4], ['a', 4], ['b', 4]] 
    >>> print groupPreserveSorted(lop) 
    [('c', 0), ('a', 1), ('a', 2), ('a', 3), ('b', 1), ('b', 2), ('b', 3), ('c', 3), ('c', 4), ('a', 4), ('b', 4)] 


    """ 
    groupCount = 0 
    groupMap = {} #map contains the "level" to the highest group 
    maxGroupDic = {} #this contains a map from tup[1] to the highest level attained by tup[1] 
    groupTypeToMapItem = {} #this contains all the levels that items in tup[0] are placed on 

    for groupType, dependencyGroup in listOfPairs: 
     if groupCount == 0: 
      groupMap[0] = [(groupType, dependencyGroup)] 
      maxGroupDic[dependencyGroup] = 0 
      groupTypeToMapItem[groupType] = [0] 
      groupCount+=1 
     else: 
      if groupType not in groupTypeToMapItem:#need to make new group 
       groupMap[groupCount] = [(groupType, dependencyGroup)] 
       maxGroupDic[dependencyGroup] = groupCount 
       groupTypeToMapItem[groupType] = [groupCount] 
       groupCount+=1 
      else: 
       maxGroupTypeItem = groupTypeToMapItem[groupType][-1] 
       if dependencyGroup in maxGroupDic: #then we just need to check where to add to a new level or to an old level 
        maxItem = maxGroupDic[dependencyGroup] 
        if maxItem>maxGroupTypeItem: #then we need to make a enw group 
         groupMap[groupCount] = [(groupType, dependencyGroup)] 
         maxGroupDic[dependencyGroup] = groupCount 
         groupTypeToMapItem[groupType] = [groupCount] 
         groupCount+=1 
        else: 
         countToUse = [item for item in groupTypeToMapItem[groupType] if item>=maxItem][0] 
         groupMap[countToUse].append((groupType, dependencyGroup)) 
         maxGroupDic[dependencyGroup]=countToUse 
       else: #we haven't added this groupType yet just add to lowest level 
        countToUse = groupTypeToMapItem[groupType][0] 
        groupMap[countToUse].append((groupType, dependencyGroup)) 
        maxGroupDic[dependencyGroup]=countToUse 

    return flatten([groupMap[count] for count in xrange(groupCount)], depth = 1) 

這是一個很好的解決方案，因爲它是O（n），但它絕對不是最乾淨的答案:)

Answer 1

這是我的解決方案

>>> data 
['c01', 'a11', 'b12', 'a21', 'b22', 'c23', 'c31', 'b32', 'a33'] 
>>> data="c01,a11,b12,a21, b22,c23, c31,b32, a33" 
>>> data=[x.strip() for x in data.split(",")] 
>>> data=sorted(data,key=operator.itemgetter(0)) 
>>> data=sorted(data,key=operator.itemgetter(1)) 
>>> data=sorted(data,key=operator.itemgetter(2)) 
>>> data 
['c01', 'a11', 'a21', 'c31', 'b12', 'b22', 'b32', 'c23', 'a33'] 
>>> 

或者作爲一個單一的在線解決方案

>>> data 
['c01', 'a11', 'b12', 'a21', 'b22', 'c23', 'c31', 'b32', 'a33'] 
>>> [data.sort(key=operator.itemgetter(x)) for x in [0,1,2]] 
>>> data 
['c01', 'a11', 'a21', 'c31', 'b12', 'b22', 'b32', 'c23', 'a33']