DjangoBB LoFi version

Полная версия: Задача о нескольких графах.

Начало » Python для новичков » Задача о нескольких графах.

OrangeGrunge

Март 6, 2017 22:13:09

Здравствуйте!
Прошу помочь в решении задачи.
Входные данные: несколько графов, заданных в виде словаря отношений вида {потомок:родитель} между объектами. Например:

 {1:2,2:3,4:3,3:None,6:5,5:None,7:None}

На выходе надо получить список списков элементов каждого графа. Для указанного примера:

 [[1,2,3,4],[6,5],[7]]

Я написал функцию и выяснил, что с небольшими входными данными она справляется. Но когда элементов порядка 20 - получаю Memory Error.
Подскажите, господа, что мне сделать, чтобы она решала более сложные варианты?

 def MakeBranches(a):
    q=[]
    for i in a:
        q.append([i])
        if a[i] != None: q[-1].extend(a[i])
    d=[]
    for i in q:
       for j in q:
          if set(i).intersection(set(j)) != set():
              i.extend(j)
       d.append(set(i))
    b=[]
    for i in d:
        if b.count(i)==0
            b.append(i)
    for i in range(0,len(b)):
        b[i]=list(b[i])
    return b

OrangeGrunge

Март 7, 2017 02:13:33

Решил сам.
Если кому-то интересно:

 def MakeBranches(a):
        q=[]
        b = dict(a)
        c = dict(a)
        for i in b:
            if b[i] == None:
                q.append([i])
                c.pop(i)
        b = dict(c)
        while len(b) != 0:
            bkey = list(b.keys())
            for i in bkey:
                for j in q:
                    if j.count(b[i]) == 1:
                        j.extend([i])
                        b.pop(i)
                        break
return q