LINUX.ORG.RU
Форум — Development  

Странное поведение функции, которая формирует дерево

 , ,


0

2

Пишу ф. form_tree, которая принимает параметр - список и формирует на его основе дерево в произвольной форме.

Пока функция в стадии доработки и отладки.
Это черновой вариант. Ф. linker - «helper function», тоже в стадии доработки.

class node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


    def insertL(self, data):
        self.left = node(data)
        return self.left

    def insertR(self, data):
        self.right = node(data)
        return self.right

linker 

def linker(root, lst):
    import random


    seq = ['left', 'right', 'nither', 'either']
    res = random.choices(seq,(0.2, 0.2, 0.1, 0.5), k=1)
    if lst:
        l=random.choice(lst)

        if res == ['left']:
            root=root.insertL(l)
            lst.remove(l)
            return root, lst
        elif res == ['right']:
            root=root.insertR(l)
            lst.remove(l)
            return root,lst
        elif res == ['nither']:
            return root,lst
        elif res == ['either']:
            print('res', res)
            nodes = [root.insertL(l)]
            lst.remove(l)
            if lst:
                l2=random.choice(lst)
                nodes+=[root.insertR(l2)]
                lst.remove(l2)
                return nodes, lst
            else:
                return nodes[0],lst
    else:
        return root, lst

основная 

def form_tree(ls):
    import random

    data = random.choice(ls)
    root=Root=node(data)
    ls.remove(data)
    nodes = None

    while ls:
        if type(nodes)!= list:
            result=linker(root, ls)
            if not result[1]:
                return Root
            else:
                ls=result[1]
            if type(result[0])!= list:
                root=result[0]
            else:
                nodes=result[0]
        else:
            new_nodes=[]
            print('nodes = ', nodes)
            for n in nodes:
                if ls:
                    result = linker(n, ls)
                    ls = result[1]
                    if type(result[0]) != list and result[0] != n:
                        new_nodes = new_nodes+[result[0]]
                    elif type(result[0]) == list:
                        new_nodes = new_nodes+result[0]
                else:
                    return Root
            nodes=new_nodes
    return Root

Согласно выставленным print в linker ('either' section) и form_tree (for-loop), при каждом запуске выводится


res ['either']
nodes =  [<__main__.node object at 0x7ffb5f0cf1d0>, <__main__.node object at 0x7ffb5f0cf940>]
nodes =  [<__main__.node object at 0x7ffb5f0cf7b8>]
res ['either']
nodes =  [<__main__.node object at 0x7ffb5f0cf8d0>,

И выдается ответ.

Но иногда ф. form-tree (на 5 или 8 запуск)начинает бесконечно выводить:

 []
nodes =  []
nodes =  []
nodes =  []
nodes =  []
nodes =  []
nodes =  []
nodes =  []

Как бы выяснить, почему?

Используемый список

ls=[1,2,3,4,5,6,7,8,9,10,11,13,12,14,15]

print(form_tree(ls))


Последнее исправление: hibiscusM (всего исправлений: 1)

Как бы выяснить, почему?

Проверяй на каждой итерации ls и nodes. По твоей логике возникает ситуация, когда ls ещё не пустой, а nodes уже [], вот тебе и бесконечный цикл.

vvn_black ★★★★★
()

Лучше сразу весь список рандомизировать и потом через итератор дергать по одному элементу. Узлы, в которые надо делать вставку, хранить лучше в очереди.

import random
from queue import Queue


def get_random_where():
    seq = ['left', 'right', 'neither', 'either']
    res = random.choices(seq, (0.2, 0.2, 0.1, 0.5), k=1)
    return res[0]


class Node(object):
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insert_left(self, data):
        self.left = Node(data)
        return self.left

    def insert_right(self, data):
        self.right = Node(data)
        return self.right


def form_tree(ls):
    if len(ls) == 0:
        raise ValueError("List is empty")
    random_list = list(ls)
    random.shuffle(random_list)
    random_list_iter = iter(random_list)

    q = Queue()
    result = Node(next(random_list_iter))
    q.put(result)

    try:
        while True:
            node = q.get()
            where = get_random_where()

            if where == 'left':
                q.put(node.insert_left(next(random_list_iter)))
            elif where == 'right':
                q.put(node.insert_right(next(random_list_iter)))
            elif where == 'neither':
                q.put(node)
            elif where == 'either':
                q.put(node.insert_left(next(random_list_iter)))
                q.put(node.insert_right(next(random_list_iter)))
    except StopIteration:
        pass

    return result
qaqa ★★
()
Ответ на: комментарий от qaqa

!!

Да... очередь и итератор делают чудеса. Спасибо за вариант.

hibiscusM
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development