分組我道歉,如果這個問題已在回答: 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),但它絕對不是最乾淨的答案:)
是否可以解決您的數據問題?['c01','a11','a21','c31','b12','b22','b32','c23','a33']如果是的話,我可以有一個可能的解決方案,您的問題 – Abhijit
是的,理論上是可行的。我只寫了一個不太優雅的解決方案。你的解決方案是什麼? – phubaba