группировка с топологией - PullRequest
Новая
       43

группировка с топологией

1 голос
/ 12 декабря 2011

Прошу прощения, если на этот вопрос уже был дан ответ в: Топологическая сортировка с группировкой

Однако я не совсем понимаю ответ, поскольку я новичок в теории графов.

У меня есть следующие предметы: 

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 </p>

a21 <-b22, b22 <-c23 </p>

c31 <-b32, b32 <-a33 </p>

c01

Отсюда я бы хотел группировать по буквам, сохраняя зависимости. Одним из таких решений будет 

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

Мы можем видеть, что a11 <-b12, a21 <-b22 <-c23, c31 <-b32 <-a33, c01 </p>

Любые мысли будут с благодарностью, Спасибо, Rob

одно решение: 

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), но это определенно не самый чистый ответ:)

1 Ответ

0 голосов
/ 12 декабря 2011

Это моё решение 

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