Блог

Я хочу рекурсивно разделить список и в конечном итоге сохранить его в древовидной структуре.

Моя цель — реализовать это с нуля, чтобы действительно понять и изучить, т. Е. Меня не интересует какой-либо модуль, предоставляющий эту функциональность.

Приведенный ниже код на самом деле не работает, поскольку я борюсь с рекурсивной функцией, которую нужно вызывать дважды (для обеих сторон разделения). В частности, у меня следующая проблема с кодом:

1. критерий min_size не выполняется
2. выходные данные должны быть в форме, в которой я могу отслеживать дочерние элементы (слева / справа) и родителей. Как мне реализовать это наилучшим образом?

Может кто-нибудь дать мне несколько советов, как улучшить мой код, чтобы он правильно разделял список рекурсивно.

Любой совет поможет. Спасибо!

 def _split(data):
    'Dummy function to split data'
    idx = np.random.randint(0,len(data),1)[0]
    lhs, rhs = data[:idx], data[idx:]
    
    return lhs, rhs
    
def tree(data, min_size=2):
        
    out = []
    
    if (len(data) <= min_size):
        
        out.append(data)
        return out
        
    else:
        
        lhs, rhs = _split(data)
    
        out.append(tree(lhs, min_size))
        out.append(tree(rhs, min_size))
        
    return out
 

Я помещаю ответ здесь, а не в комментариях, поскольку это позволит улучшить форматирование, хотя я сомневаюсь, что это полный ответ…

1. Соблюдение min_size

Как я уже сказал в комментарии, вы должны убедиться, что не разделяете массивы, которые меньше, чем 2*min_size с тех пор вы не сможете разделить их на два массива, которые больше или равны min_size . Вы также должны убедиться, что ограничили индекс разделения, чтобы случайно не создавать массивы размером меньше min_size

 def _split(data, min_size):
    'Dummy function to split data'
    # Create a random split index between `min_size` and `len(data)-min_size`
    idx = np.random.randint(min_size,len(data)-min_size 1)
    lhs, rhs = data[:idx], data[idx:]
    
    return lhs, rhs
    
def tree(data, min_size=2):
    out = []
    
    if (len(data) < 2*min_size):  
        # out.append(data)
        # You do not have to wrap the final layer in another array
        return data
        
    else:
        
        lhs, rhs = _split(data,min_size)
    
        out.append(tree(lhs, min_size))
        out.append(tree(rhs, min_size))
        
    return out
 

Вывод для массива от 1 до 12:

 [[[1, 2], [3, 4]], [[[5, 6], [7, 8]], [[9, 10], [11, 12]]]]
 

Я также реализовал альтернативный метод со словарями, который может быть немного легче читать. Но это все еще не позволяет выполнить простой обход вверх по дереву.

 def tree2(data, min_size=2):
    
    if (len(data) < 2*min_size):  
        # out.append(data)
        # You do not have to wrap the final layer in another array
        return data
        
    else:
        
        lhs, rhs = _split(data,min_size)
        return {
            "left": tree2(lhs, min_size),
            "right": tree2(rhs, min_size)
        }
 

Вывод:

 {'left': [1, 2], 'right': {'left': {'left': [3, 4], 'right': [5, 6]}, 'right': {'left': {'left': [7, 8], 'right': [9, 10]}, 'right': [11, 12]}}}
 

Что касается второго пункта, я не совсем уверен в том, как лучше всего это сделать, это зависит от того, какие именно операции вы ожидаете сформировать в структуре данных.

Одна из идей заключается в использовании классов. Возможно, это немного перепроектировано для вашей проблемы, но вы можете полностью пройти по дереву, взяв Tree.parent , Tree.right , Tree.left :

 class Tree:
    def __init__(self, data=None, level=0):
        self.left = None
        self.right = None
        self.parent = None
        
        self.data = data
        self.level = level
    
    def set_left_right(self, left, right):
        self.left = left
        self.right = right
    
    def set_parent(self, parent):
        self.parent = parent


    def __str__(self):

        if self.data == None:
            data = "*{}*".format(self.level)
        else:
            data = self.data

        if self.left != None and self.right != None:
            return "[{}]<-({})->[{}]".format(self.left, data, self.right)
        elif self.left != None:
            return "[{}]<-({})".format(self.left, data)
        elif self.right != None:
            return "({})->[{}]".format(data, self.right)
        else:
            return "({})".format(data)




def tree3(data, min_size=2, level=0):
    
    if (len(data) < 2*min_size):  
        return Tree(data, level=level)
        
    else:
        
        lhs, rhs = _split(data,min_size)

        lhs = tree3(lhs, min_size,level 1)
        rhs = tree3(rhs, min_size,level 1)

        out = Tree(level=level)
        lhs.set_parent(out)
        rhs.set_parent(out)

        out.set_left_right(lhs, rhs)

        return out


print(tree3([1,2,3,4,5,6,7,8,9,10,11,12]))
 

Вывод:

 [[[([1, 2])]<-(*2*)->[([3, 4, 5])]]<-(*1*)->[([6, 7])]]<-(*0*)->[[([8, 9, 10])]<-(*1*)->[([11, 12])]]