与拓扑

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