Создание дерева из списка комбинаций элементов - PullRequest
Новая
       14

Создание дерева из списка комбинаций элементов

1 голос
/ 11 октября 2011

У меня есть n списков A, B, C ..., которые содержат элементы a, b, c ....Я использую их для создания списков возможных комбинаций (списка списков), чтобы первый элемент был взят из таблицы A, второй - из B и т. Д. Каков наилучший способ преобразования этой плоской структуры в дерево, за которым следует кореньэлементами списка A, каждый из которых имеет все элементы списка B и т. д., создавая тем самым каждую возможную комбинацию в форме пути от корня?

1 Ответ

3 голосов
/ 11 октября 2011

Алгоритмы

1: Исходя из ввода

Итак, если у вас есть списки [1, 2, 3], [4, 5, 6], [7, 8, 9], у вас есть этот список возможных перестановок

Итак, я бы сейчас просмотрел списки и их элементы.Все представляют пути дерева, который вы хотите.Поэтому, если бы все было помещено в дерево, я смог бы найти узел 1, затем перейти к 4 и затем найти 7 на третьем уровне.Если нет, я должен добавить это туда. 

paths = [
    [1, 4, 7], [1, 4, 8], [1, 4, 9], [1, 5, 7], [1, 5, 8], [1, 5, 9], [1, 6, 7], [1, 6, 8], [1, 6, 9], [2, 4, 7], [2, 4, 8], [2, 4, 9], [2, 5, 7], [2, 5, 8], [2, 5, 9], [2, 6, 7], [2, 6, 8], [2, 6, 9], [3, 4, 7], [3, 4, 8], [3, 4, 9], [3, 5, 7], [3, 5, 8], [3, 5, 9], [3, 6, 7], [3, 6, 8], [3, 6, 9]
]

class Tree(object):
    def __init__(self, node=None):
        self.node = node
        self.children = []

    def addChild(self, child):
        self.children.append(child)

    def toList(self):
        if len(self.children) > 0:
            return [self.node, [x.toList() for x in self.children]]
        else:
            return [self.node]

tree = Tree()

# iterate through the lists
for path in paths:
    subtree = tree

    for value in path:
        # check whether the current value already exists at this position in the tree
        found = False
        for child in subtree.children:
            if value == child.node:
                subtree = child
                found = True
                break

        # attach the leaf to the current position in the tree if needed
        if not found:
            newchild = Tree(node=value)
            subtree.addChild(newchild)
            subtree = newchild

        # use the found or created leaf as a position for the next value in the path-list

print tree.toList()

2: Вернуться к исходным спискам

Если дерево настолько симметрично, как кажется, вы также можете просто нарезатьуровни деревьев, давая вам списки A, B и C. Затем вы возвращаетесь на круги своя и можете построить дерево: 

paths = [
    [1, 4, 7], [1, 4, 8], [1, 4, 9], [1, 5, 7], [1, 5, 8], [1, 5, 9], [1, 6, 7], [1, 6, 8], [1, 6, 9], [2, 4, 7], [2, 4, 8], [2, 4, 9], [2, 5, 7], [2, 5, 8], [2, 5, 9], [2, 6, 7], [2, 6, 8], [2, 6, 9], [3, 4, 7], [3, 4, 8], [3, 4, 9], [3, 5, 7], [3, 5, 8], [3, 5, 9], [3, 6, 7], [3, 6, 8], [3, 6, 9]
]

lists = [[]]*len(paths[0])
for i in xrange(len(paths[0])):
    lists[i] = set([])
    for l in paths:
        lists[i].add(l[i])

def iterate(listnumber):
    result = []
    for element in lists[listnumber]:
        if listnumber < len(lists)-1:
            result.append([element, iterate(listnumber+1)])
        else:
            result.append([element])
    return result

tree = iterate(0)

print tree

Он проходит через каждый слой кучи списков (а, б, в) и сохраняет уникальные элементы в списке.Затем он имеет списки A, B, C и генерирует из него дерево.

Результат

Это дерево, которое я получаю, 0 - это искусственный корень.Узлы «перерабатываются», поскольку все они несут одинаковое содержимое.(Сделано с точка .)

http://wstaw.org/m/2011/10/11/tree.png

...