0

Existe a seguinte lista:

[
    [0, False],
    [1, True],
    [1, False],
    [2, False],
    [2, True],
    [2, False],
    [3, False],
    [3, True],
    [2, False],
    [1, False],
    [2, False]
]

Esta lista forma a seguinte árvore:

árvore de dados

Como podem observar, a lista respeita a ordem que diz respeito a ramificação de cada item, logo numa ordem como (exemplo) 1, 2, 3, 2, 1 diz que a primeira ocorrência 2 pertence ao primeiro 1, e o 3 pertence ao primeiro 2, já a segunda ocorrência do 2 pertence ao primeiro 1, e o último 1 não possui ramificação.

Não consegui resolver esse problema, achei que pudesse usar recursividade, mas os itens da lista estão ordenados, cada próximo item da lista pode se relacionar com os anteriores. Bom, não sei como resolver, o resultado esperado é saber quantos porcentos dessa árvore foi resolvido. Nesse exemplo que citei o resultado calculado deu 45,83% da arvore resolvida.

Explicação da árvore da questão:

A ramificação de nível 3 está com 50% resolvida (um True e outro False), ela pertence a um ramo do nível 2, logo esse ramo tem valor de 50%. Esses quatro ramos de nível 2 tem um total de (0% + 100% + 50%+ 0%) que dividido por 4 é igual a 37,5%. Então existe no nível 1 um ramo de 100% outro de 37,5% e outro de 0%, que divido por três da 45,83%

Como resolver isso em Python?

6
  • O que significa estar "resolvido"?
    – Juan Lopes
    Commented 14/03/2016 às 22:30
  • @JuanLopes resolvido é quando está True
    – Paulo
    Commented 14/03/2016 às 22:57
  • Nenhuma fração de denominador 11 (o número de nós na árvore) arredonda para 45,83%. Você poderia explicar o resultado, por favor?
    – Juan Lopes
    Commented 14/03/2016 às 23:17
  • @JuanLopes creio que a explicação está bem clara. A ramificação de nível 3 está com 50% resolvida (um True e outro False), ela pertence a um ramo do nível 2, logo esse ramo tem valor de 50%. Esses quatro ramos de nível 2 tem um total de (0% + 100% + 50%+ 0%) que dividido por 4 é igual a 37,5%. Então existe no nível 1 um ramo de 100% outro de 37,5% e outro de 0%, que divido por três da 45,83%.
    – Paulo
    Commented 15/03/2016 às 3:20
  • Não tinha ficado clara. A interpretação que tinha dado inicialmente era "qual o percentual de nós está resolvido?", e não "qual o percentual de sub-árvores está resolvido, recursivamente?". Mas agora entendi. Só acho que isso deveria estar no corpo da pergunta.
    – Juan Lopes
    Commented 15/03/2016 às 11:00

2 Respostas 2

1

Você pode navegar pela árvore implicitamente calculando o total resolvido pelos filhos de cada nó, assim:

def complete(tree, i, level):
    first = i
    siblings = []
    while i < len(tree) and tree[i][0] == level:
        count, value = complete(tree, i+1, level+1)
        siblings.append(max(int(tree[i][1]), value))
        i += count + 1

    return (i - first, float(sum(siblings))/len(siblings or [0]))


L = [
    [0, False],
    [1, True],
    [1, False],
    [2, False],
    [2, True],
    [2, False],
    [3, False],
    [3, True],
    [2, False],
    [1, False],
    [2, False]
]

print complete(L, 0, 0)
1

Python é uma linguagem legal por que não costuma ficar entre "você e o problema" - nesse caso, acho que levei mais tempo para entender como você chegou nesse 45.83% do que para pensar numa forma de resolver a questão.

Bom, é necessário representar para o computador cada elemento da lista com as propriedades que ele tem - no caso, cada elemento tem uma lista de outros elementos dependentes de si e uma % de quanto está resolvido. Se o elemento tem "filhos" essa porcentagem de quanto está resolvido é igual a da lista de filhos - senão, é dada pelo valor na sua lista.

Essa representação da lista é uma forma mínima de dar toda a informação necessária, mas não ajuda a resolver o problema - precisamos sim de uma classe Nó que tem as duas propriedades que eu citei: coeficente de quanto está completo, e lista de filhos - e a partir da sua lista dada criamos essa árvore - podemos ter o requinte de usar o decorator "property" do Python para o coeficiente de quanto está completo - isso faz com que a leitura de um coeficiente de completo seja na verdade a chamada de uma função que calcula o valor em tempo real.

class Node(object):
    def __init__(self, completeness=0):
        self._completeness =  float(completeness)
        self.children = []

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

    @property
    def completeness(self):
        if self._completeness or not self.children:
            return self._completeness
        return sum(child.completeness for child in self.children) / len(self.children)

(Se não conhecer a sintaxe que usei na última linha -de generator expression, vale a pena conferir a documentação: https://www.python.org/dev/peps/pep-0289 - esse código também tira proveito do valor numérico do "True" em Python ser "1", por razões históricas - se não fosse isso, seria necessário mais um "if")

Bom -essa é a classe como foi descrita anteriormente - só que para ela descrever o problema é necessário criar uma árvore com nós desta classe a partir da sua lista de entrada - isso pode ser feito com mais uma função - ela é complicadinha, mas perceba pelos comentários que é exatamente comoteriamos que proceder se estivessemos cosntruindo essa árvore "em papel", desenhando cada nó a medida que o processacemos a partir da lista de entrada:

def build_tree(source):
    # transforma a lista num iterador:
    # isso permite que tomemos o primeiro elemento com a função "next"
    # e guardemos os demais elementos para serem consumidos pelo "for" abaixo.
    source = iter(source)
    # consome o primeiro nó na lista, criando a raiz da árvore)
    level, completeness = next(source)
    root = Node(completeness)
    # lista temporária que permite subir para os nós superiores
    # quando cada ramo for preenchido:
    tree_stack = [(level, root)]
    for level, completeness in source:
        new_node = Node(completeness)

        # se estamos de volta num nó pelo menos um nível acima do anterior -  remover
        # elementos da lista temporária - o nó que ficar por último
        # nessa lista será o último nó inserido com nível acima do
        # atual (portanto, o pai do atual)
        while tree_stack[-1][0] > level:
            tree_stack.pop()
        previous_level = tree_stack[-1][0]

        if level == previous_level:
            # o mesmo nível do último nó inserido -
            # inserir o novo nó como irmão do último 
            tree_stack[-2][1].add_child(new_node)
            # remover o irmão do nó atual da lista temporária - 
            # de forma que o penultimo elemento seja o sempre o 
            # pai de outros nós no nível atual
            tree_stack.pop()
        elif level > previous_level:
            #colocar o novo nó como filho do último nó criado
            tree_stack[-1][1].add_child(new_node)
        tree_stack.append((level, new_node))
    return root

E, de forma que o programa rode com seus dados de exemplo, quando for invocado como "stand alone" podemos adicionar esta parte - (uso a própria formatação de strings do Python para exibir o valor do coeficiente de completude como porcentagem):

if __name__ == "__main__":
    data = [
    [0, False],
    [1, True],
    [1, False],
    [2, False],
    [2, True],
    [2, False],
    [3, False],
    [3, True],
    [2, False],
    [1, False],
    [2, False]
]
    tree = build_tree(data)
    print ("A porcentagem de completude da árvore é {:.02%}".format(tree.completeness)
4
  • Apesar de solucionar o meu problema, achei a solução de Juan mais simples, não sei em relação a perfomance qual se sai melhor, de qualquer forma obrigado!
    – Paulo
    Commented 15/03/2016 às 15:01
  • Não se trata de performance - esta é a solução para montar a árvore em Python e fazer operações nela. aA outra resposta dá um jeito de fazer o cálculo usando a representação da árvore do jeito que chega para você, sem ter que montar uma estrutura de dados genérica. Se é um problema de maratona, ou de escola - a outra resposta é a "desejada" - pois chegou num algoritimo bom para fazer as manipulações para chegar no número desejado. Se for parte de um problema do mundo real - a abordagem de montar os objetos reais e ter um sistema mantível é mais importante.
    – jsbueno
    Commented 15/03/2016 às 18:49
  • Isso não é uma questão de faculdade, entendo seu ponto de vista, no entanto o problema em questão é apenas para calcular o percentual da árvore e imprimir o valor, depois disso os dados não são mais reutilizados, por isso a solução de Juan foi mais interessante no meu caso. De qualquer forma valeu!
    – Paulo
    Commented 15/03/2016 às 21:11
  • 1
    sim, se você só precisa desse número e mais nada, a resposta dele deve ser a aceita.
    – jsbueno
    Commented 15/03/2016 às 21:12

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .