与拓扑
问题描述:
分组我道歉,如果这个问题已在回答: 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),但它绝对不是最干净的答案:)
答
这是我的解决方案
>>> 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']
+0
这很有趣:)肯定比我的解决方案更容易! – phubaba
是否可以解决您的数据问题?['c01','a11','a21','c31','b12','b22','b32','c23','a33']如果是的话,我可以有一个可能的解决方案,您的问题 – Abhijit
是的,理论上是可行的。我只写了一个不太优雅的解决方案。你的解决方案是什么? – phubaba