Прошу прощения, если на этот вопрос уже был дан ответ в: Топологическая сортировка с группировкой
Однако я не совсем понимаю ответ, так как я новичок в теории графов.
У меня есть следующие предметы:
c01,a11,b12,a21, b22,c23, c31,b32, a33.
Каждый из них представляет собой три кортежа.
Tup[0]
: 'буква для группировки'
Tup[1]
: 'номер группы, в которой допустимы зависимости'
Tup[2]
: 'порядок сортировки зависимостей'
Я хотел бы сгруппировать по tup[0]
как можно точнее, сохраняя при этом порядок сортировки, описанный группами в item[1]
и item[2]
. Пункты 1,2 позволяют нам создавать зависимости, отсюда нам просто нужно создать группы.
поэтому мы можем создать следующие зависимости:
a11<-b12
a21<-b22, b22<-c23
c31<-b32, b32<-a33
c01
Отсюда я хотел бы сгруппировать по буквам, сохраняя при этом зависимости. Одним из таких решений будет
a11, a21, b12, b22, c01, c23, c31, b32, a33
Мы видим, что a11‹-b12, 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']
быть возможным решением для ваших данных? Если да, у меня есть возможное решение вашей проблемы - person Abhijit   schedule 12.12.2011