all_n_nodes_trees.py

import random
import yaml
import json
from pprint import pprint
from anytree import Node, RenderTree
from anytree.exporter import DotExporter
from itertools import count,groupby,combinations_with_replacement
from pandas.core.common import flatten
from anytree import AnyNode,PreOrderIter
from anytree.exporter import DictExporter
from anytree.importer import DictImporter

def tree_str(tree):
    result = ""
    for pre,fill,node in RenderTree(tree):
        result += "%s%s" % (pre, node.name) + "\n"
    return result

def print_tree(tree):
    print(tree_str(tree))

def serialize_tree_str(tree):
    dct = DictExporter().export(tree)
    return yaml.dump(dct, default_flow_style=False)

def print_serialize_tree(tree):
    print(serialize_tree_str(tree))

def deserialize_tree(tree_str):
    dct = yaml.load(tree_str, Loader=yaml.FullLoader)
    return DictImporter().import_(dct)

def deep_copy_tree(tree):
    return deserialize_tree(serialize_tree_str(tree))

def serialize_childs_possibilities(childs_possibilities):
    possibilities = []
    for child_possibilities in childs_possibilities:
        tmp_list = []
        for possibility in child_possibilities:
            dct = DictExporter().export(possibility)
            tmp_list.append(dct)
        possibilities.append(tmp_list)
    return json.dumps(possibilities)

def deserialize_childs_possibilities(childs_possibilities_str):
    data = json.loads(childs_possibilities_str, strict=False)
    possibilities = []
    for child_possibilities in data:
        tmp_list = []
        for possibility in child_possibilities:
            tree = DictImporter().import_(possibility)
            tmp_list.append(tree)
        possibilities.append(tmp_list)
    return possibilities

def repart(R, N, M = None):
    start = min(M,R) if M != None else R
    possibilities = []
    for i in range(start,0,-1):
        left = R-i
        if N-1 < left:
            break
        b = [0] * N
        b[-1] = i
        if left == 0:
            possibilities.append(b)
        elif left == 1:
            b[-2] = 1
            possibilities.append(b)
        elif left > 1:
            leftPossibilities = repart(left, N-1, i)
            for p in leftPossibilities:
                concat = p
                concat.append(i)
                possibilities.append(concat)
    return possibilities

def make_tree(root_childs):
    root = Node("R")
    for a in range(1,root_childs+1):
        Node(f"{a}", parent=root)
    return root

def apply_child_possibility(base_tree, order):
    tmp_tree = make_tree(len(order))
    tmp_tree.children = list(map(lambda x: deep_copy_tree(x), order))
    return tmp_tree

def apply_childs_possibilities_generator(base_tree, child_ps):
    list_child_ps = list(child_ps)
    for index,order in enumerate(all_combinations_generator(list_child_ps)):
        result = apply_child_possibility(base_tree, order)
        yield result

def order_to_values(list_set, order):
    return list(map(lambda args: list_set[args[0]][args[1]], enumerate(order)))

def all_combinations_generator(list_set):
    if len(list_set) == 1:
        for p in list_set[0]:
            yield [ p ]
        return
    last_index = len(list_set)-1
    current_index = last_index
    current_order = [0]*len(list_set)
    yield order_to_values(list_set, current_order)
    while True:
        current_order_index = current_order[current_index]
        current_max_order_index = len(list_set[current_index])-1
        if current_order_index == current_max_order_index:
            current_order[current_index] = 0
            current_index -= 1
            if current_index == 0 and \
                    current_order[current_index] == len(list_set[current_index])-1:
                break
        else:
            current_order[current_index] += 1
            yield order_to_values(list_set, current_order)
            if current_index < last_index:
                current_index = last_index

def apply_repartition(tree, repartitions):
    # print(f"repartition: {repartition}")
    # child_possibilities = [Node("empty")]*len(repartition)
    # for index,r in enumerate(repartition):
    #     if r == 0:
    #         tmp_node = deep_copy_tree(tree.children[index])
    #         tmp_node.parent = None
    #         child_possibilities[index] = [ tmp_node ]
    #     elif r == 1:
    #         tmp_child = deep_copy_tree(tree.children[index])
    #         tmp_child.parent = None
    #         tmp_node = Node("1", parent=tmp_child)
    #         child_possibilities[index] = [ tmp_child ]
    #     elif r > 1:
    #         child_possibilities[index] = list(trees_with_n_nodes(r+1))
    groups_possibilities = []
    for r, g in groupby(repartitions):
        group_c_possibilities = []
        if r == 0:
            group_c_possibilities = [ make_tree(0) ]
        elif r == 1:
            group_c_possibilities = [ make_tree(1) ]
        elif r > 1:
            group_c_possibilities = list(trees_with_n_nodes(r+1))
        # print(f"repartitions: {repartitions}, r={r}, possibilities:")
        # for p in group_c_possibilities:
        #     print("p: ")
        #     print_tree(p)
        groups_possibilities.append(list(
                combinations_with_replacement(group_c_possibilities, len(list(g)))
            )
        )
    # print("Results:")
    # for ps in groups_possibilities:
    #     print("Group:")
    #     for i,c in enumerate(ps):
    #         print(f"combination#{i+1}")
    #         for p in c:
    #             print_tree(p)
    #             print(serialize_tree_str(p))
    #     print("________")
    for combination in all_combinations_generator(groups_possibilities):
        childs = list(flatten(combination))
        # print(f"childs: {childs}")
        # print("tree:")
        # print_tree(tree)
        yield apply_child_possibility(tree, childs)

def trees_with_n_nodes(N):
    current_invocation = random.randint(0,1000)
    for root_childs in range(N-1, 0, -1):
        tree = make_tree(root_childs)
        left = N-root_childs-1
        if (left == 0):
            yield tree
        elif (left == 1):
            child = Node("1", parent=tree.children[-1])
            yield tree
        elif (left > 1):
            repartitions = repart(left, root_childs)
            for repartition in repartitions:
                # print(f"Internal repartition: {repartition}")
                for t in apply_repartition(tree, repartition):
                    yield t

# def group_by_siblings(tree):
#     nodes = list(PreOrderIter(tree.root))
#     def parent_key(node):
#         if node.parent != None:
#             path_str = '/'.join([node.name for node in node.parent.path])
#             return path_str
#         else:
#             return ""
#     result = []
#     for k, g in groupby(sorted(nodes, key=parent_key), key=parent_key):
#         result += [ list(g) ]
#         # print(f"group: {[node.name for node in list(g)]}")
#         # groups.append(list(g))
#         # uniquekeys.append(k)
#     return result

# def apply_group_repartition(groups, group_repartition):
#     for g,rs in zip(groups,group_repartition):
#         for n,r in zip(g, rs):
#             new_nodes = [ Node(f"{i+1}") for i in range(r)]
#             n.children = (new_nodes+list(n.children))[::-1]


# base_tree_data = \
# '''
# children:
# - children:
#   - name: '4'
#   name: '2'
# - name: '3'
# name: '1'
# '''

# base_tree = deserialize_tree(base_tree_data)
# print_tree(base_tree)
# groups = group_by_siblings(base_tree)
# print(groups)
# repartition = [[2], [1, 1], [1]]
# apply_group_repartition(groups, repartition)
# print_tree(base_tree)
counter = 0
for tree in trees_with_n_nodes(6):
    counter += 1
    # print(counter)
    print("Final Possibility: ")
    print_tree(tree)
print(counter)
print(f"{counter} possible trees")