Запись успеха / неудач из списка событий с использованием двоичного дерева

Question

У меня есть список событий ['one', 'two', 'three']. Эти события могут либо пройти, либо потерпеть неудачу. Я хочу построить дерево решений для записи возможных результатов, а именно:

                    <root>
                      /\
      <one_pass>              <one_fail>
          /\                      /\
<two_pass>  <two_fail>  <two_pass>  <two_fail>
...

Из множественного отлично ответов , я вижу, что рекурсия - это путь для этого, по-видимому, в сочетании с двоичным деревом. С чем я борюсь, так это с циклом построения проходов / неудач на каждом уровне ... Это цикл for или я использую рекурсию?

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

class Node:
    def __init__(self, data, children=None):
        if children is None:
            children = []
        self.data = data
        self.children = children

    def __str__(self):
        return str(self.data)

    __repr__ = __str__

def get_all_paths(node, path=None):
    paths = []
    if path is None:
        path = []
    path.append(node)
    if node.children:
        for child in node.children:
            paths.extend(get_all_paths(child, path[:]))
    else:
            paths.append(path)
    return paths

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

tree = Node("start", [
        Node("one_pass", [
            Node("two_pass"), 
            Node("two_fail")
        ]),
        Node("one_fail", [
            Node("two_pass"),
            Node("two_fail")
        ])
    ])

Из-за этого я застрял на уровне цикла for, что заставляет меня думать, что я не знаю, какой подход использовать здесь. Если цикл создал два узла на каждом проходе - в основном создавая левый и правый дочерние узлы за одну итерацию - как мне связать их с предыдущим узлом? Нужен ли метод, который делает что-то вроде следующего псевдокода?

for event in events:
    insert_node(my_tree, event, "pass")
    insert_node(my_tree, event, "fail")

NB. У меня есть 15 уровней дерева, если это что-то затрагивает.

Answer 1

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

Если все ваши условия известны заранее, очень легко рассмотреть ваш список ['pass', 'fail', 'pass', 'fail' etc..] как двоичное число ([1, 0, 1, 0]: 10), которое можно использовать в качестве индекса в списке, предварительно выделенном для длины от всех возможных результатов (2 ^N , где N - количество условий).

Если вам нужно хранить значения на каждом этапе принятия решения (т.е. сохранять значение для ['pass','fail'], а также ['pass', 'fail', 'fail']), это немного сложнее, но все же не так сложно. Мы знаем, что любое количество условий дает 2 ^N возможных результатов, поэтому мы также можем знать, сколько результатов дано при N-1 условиях, N-2 и т. Д. Всего имеется 2 ^N -1 условий всех более коротких списков условий перед условиями 2 ^N , которые относятся к N условиям. Добавляя наше двоичное число, как мы его нашли ранее, к 2 ^N -1, мы можем получить уникальный индекс для каждого возможного списка условий.

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

с учетом вашего примера:

                        <root> (0)
                    /               \
          <one_pass> (1)           <one_fail> (2)
             /     \                     /     \
    <two_pass>(3) <two_fail>(4) <two_pass>(5) <two_fail>(6)
      /  \          /  \           /   \           /    \
   (7)  (8)      (9)    (10)     (11)   (12)    (13)    (14)
 /  \   /   \   /   \   /   \   /   \   /   \   /   \   /   \
15, 16, 17, 18| 19, 20, 21, 22| 23, 24, 25, 26| 27, 28, 29, 30

отсюда легко придумать некоторые функции для преобразования списка ['pass', 'fail', 'pass', 'fail'] в индекс:

def list_to_number(L):
    acc = 0
    for item in L:
        acc *= 2 #shift number left as we shift in values from the right
        if item == 'fail': #assumes pass == 0 fail == 1
            acc += 1
    return acc


def idx(L): 
    return 2**len(L) - 1 + list_to_number(L)

Полный пример:

#  Assume we will never have more than 4 events:
#  With 4 events we have 2**4 outcomes.
#  In total there are 2**5-1 possible outcomes including intermediate steps.
#  We will preallocate a list filled with `None` to length 2**5-1 so we have 
#    enough space for all possible outcomes.
tree_data = [None]*(2**5-1)

#insert value 42 given [event_1_pass, event_2_pass, event_3_fail]
tree_data[idx(['pass', 'pass', 'fail'])] = 42

#insert value 56 given [event_1_pass, event_2_pass, event_3_pass, event_4_pass]
tree_data[idx(['pass', 'pass', 'pass', 'pass'])] = 56

#retrieve value given [event_1_pass, event_2_pass, event_3_fail]
print(tree_data[idx(['pass', 'pass', 'fail'])])
# prints: 42

#retrieve value given [event_1_fail, event_2_pass, event_3_fail]
print(tree_data[idx(['fail', 'pass', 'fail'])])
# prints: None because we never stored anything there.

Answer 2

Вы можете сгенерировать ваше дерево, используя следующий код (не рекурсивный):

def generate_nodes(parent, data):  # adds data_pass and data_fail child nodes to parent
    passed = Node(data + '_pass')
    failed = Node(data + '_fail')
    parent.children.append(passed)
    parent.children.append(failed)

    return [passed, failed]  # returns new nodes


events = ['one', 'two', 'three']
root = Node('root')  # root of our tree
current_level_events = [root]  # nodes of currently processed level

for data in events:  # go through all events
    tmp = []
    for event in current_level_events:
        tmp += generate_nodes(event, data)  # generate events 
    current_level_events = tmp

Рекурсивная реализация:

events = ['one', 'two', 'three']

def generate_nodes(parent, index):
    if index >= len(events):  # we finished tree generation, no more events found
        return
    data = events[index]
    passed = Node(data + '_pass')
    failed = Node(data + '_fail')
    parent.children.append(passed)
    parent.children.append(failed)
    # generate children for passed and failed nodes
    generate_nodes(passed, index + 1)
    generate_nodes(failed, index + 1)


events = ['one', 'two', 'three']
root = Node('root')  # root of our tree

generate_nodes(root, 0)  # starts tree generation