Mar 06, 2017, 02:43 PM

elhoria do algoritmo para enumerar árvores binári

Atualmente, eu posso enumerar rooted planar não marcadorvores binárias usando o seguinte código Prolog de força brut

e --> u | b | t.
u --> ['[op(u),['], e, [']]'].
b --> ['[op(b),['], e, [','], e, [']]'].
t --> ['number(n)'].

ota: Veja as listagens de saída abaix

e produza-os em tamanho crescente usando

es(S) :-
    length(Ls, _),
    phrase(e, Ls),     % or e(Ls,[]),
    atomic_list_concat(Ls,S).

No entanto, este é um algoritmo ineficiente de força brut

xiste um algoritmo mais eficiente para enumerar árvores binárias planas não rotuladas enraizada

Nota: As árvores podem ser geradas usando as árvores das duas iterações anteriores, pense nos números de Fibonacci e adicionando um ramo unário ou um ramo binário, no entanto, isso leva à duplicação de árvores. Eu mesmo poderia fazer essa versão, o que estou procurando é um algoritmo que gere as árvores de maneira eficiente da primeira vez, sem duplicata

Nota: Uma árvore binária também é conhecida como árvore de expressão binária ou Árvore K-ary com K <= 2.

SuplementResultado

Minha versão de força bruta para M (15) levou 1 hora e 27 minutos, enquanto a versão eficiente para M (15) levou cerca de 2 segundo

bviamente, o algoritmo eficiente é exatamente isso, muito mais eficiente e por que eu fiz a pergunt

Motzkin numbers

O número de árvores que têmNs nós @ para árvores binárias planas não rotuladas planeadas com raiz são dados pelos números de Motzkin. Veja: OEIS A001006

Nodes  Trees
1      1
2      1
3      2
4      4
5      9

O número de árvores que possuem N nós internos para uma árvore binária planar não rotulada e enraizada é dado por números catalães. Existe um algoritmo mais eficiente para gerar árvores binárias planas enraizadas usando números catalães.

Nota
O número de árvores com base nos números catalães donã têm ramos unários e contam apenasintern nós.

enquant

o número de árvores com base nos números de MotzkinFa têm ramos unários e contamtodo nós.

Vejo
OEIS A000108
Catalan Numbers por Tom Davis

Relacionar elementos da lista de prólogo ao número Motzkin

% M is Motzkin number, N is number of  list elements passed to atomic_list_concat\2
m_to_n(1,1).
m_to_n(2,3).
m_to_n(M,N) :-
    M > 2,
    N is (M*2)-1.

es_m(M,S) :-
    m_to_n(M,N),
    length(Ls,N),
    e(Ls,[]),
    atomic_list_concat(Ls,S).

statísticas com versão ineficiente de força bru

es_c(M,Count) :-
    aggregate_all(count, es_m(M,_), Count).

?- time(es_c(1,Count)).
% 57 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
Count = 1.

?- time(es_c(2,Count)).
% 141 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
Count = 1.

?- time(es_c(3,Count)).
% 571 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
Count = 2.

?- time(es_c(4,Count)).
% 2,740 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
Count = 4.

?- time(es_c(5,Count)).
% 13,780 inferences, 0.000 CPU in 0.001 seconds (0% CPU, Infinite Lips)
Count = 9.

?- time(es_c(6,Count)).
% 70,072 inferences, 0.000 CPU in 0.002 seconds (0% CPU, Infinite Lips)
Count = 21.

?- time(es_c(7,Count)).
% 357,358 inferences, 0.016 CPU in 0.012 seconds (136% CPU, 22870912 Lips)
Count = 51.

?- time(es_c(8,Count)).
% 1,824,082 inferences, 0.063 CPU in 0.056 seconds (111% CPU, 29185312 Lips)
Count = 127.

?- time(es_c(9,Count)).
% 9,313,720 inferences, 0.297 CPU in 0.290 seconds (102% CPU, 31372531 Lips)
Count = 323.

?- time(es_c(10,Count)).
% 47,561,878 inferences, 1.469 CPU in 1.467 seconds (100% CPU, 32382555 Lips)
Count = 835.

?- time(es_c(11,Count)).
% 242,896,160 inferences, 7.672 CPU in 7.665 seconds (100% CPU, 31660599 Lips)
Count = 2188.

?- time(es_c(12,Count)).
% 1,240,493,974 inferences, 38.797 CPU in 38.841 seconds (100% CPU, 31974069 Lips)
Count = 5798.

?- time(es_c(13,Count)).
% 6,335,410,822 inferences, 206.047 CPU in 213.116 seconds (97% CPU, 30747425 Lips)
Count = 15511.

?- time(es_c(14,Count)).
% 32,356,235,848 inferences, 1016.156 CPU in 1018.955 seconds (100% CPU, 31841792 Lips)
Count = 41835.

?- time(es_c(15,Count)).
% 165,250,501,417 inferences, 5231.766 CPU in 5268.363 seconds (99% CPU, 31585991 Lips)
Count = 113634.

Referência

Um livro para download gratuito como PDF que pode ajudar é "Combinatória Analítica" de Philippe Flajolet e Robert Sedgewick

Consulte também as referências noCatalã tag.

Motzkin numbers

BNF

<expression> ::= 
      <unary expression>
    | <binary expression>
    | <terminal>

<unary expression> ::= 
    "(u" <expression> ")"

<binary expression> ::= 
    "(b" <expression> " " <expression> ")"

<terminal> ::= 
    "t"

Usingrespond por David Eisenstat

Pense nelas como notas, ou migalhas de pão, para mim, caso precise usá-lo novamente em vários meses depois de esquecê-l

Para testar a resposta que usei WSL (Windows Subsystem para Linux) com o Python 3 instalado

Usando o Windows 10, criei um arquivo chamadomotzkin.py no diretório

C:\Users\Eric\Documents\Prolog

com o código Python

def ubtrees(n):
    if n == 1:
        yield 't'
    elif n > 1:
        for t in ubtrees(n - 1):
            yield '(u {})'.format(t)
        for i in range(1, n - 1):
            for t1 in ubtrees(i):
                for t2 in ubtrees(n - 1 - i):
                    yield '(b {} {})'.format(t1, t2)

depois, na WSL, criei um link simbólico para o diretório do Windows Prolog

$ ln -s "/mnt/c/Users/Eric/Documents/Prolog" /home/eric/Prolog

e alterado para o diretório WSL Prolog

$ cd Prolog

then começou o Python3

~/Prolog$ python3

e importou o código Python

>>> import motzkin

e executou o seguinte com o argumento de ubtrees sendo o número Motzkin

>>> for value in ubtrees(1):
...   print(value)
...
t

>>> for value in ubtrees(2):
...   print(value)
...
(u t)

>>> for value in ubtrees(3):
...   print(value)
...
(u (u t))
(b t t)

>>> for value in ubtrees(4):
...   print(value)
...
(u (u (u t)))
(u (b t t))
(b t (u t))
(b (u t) t)

>>> for value in ubtrees(5):
...   print(value)
...
(u (u (u (u t))))
(u (u (b t t)))
(u (b t (u t)))
(u (b (u t) t))
(b t (u (u t)))
(b t (b t t))
(b (u t) (u t))
(b (u (u t)) t)
(b (b t t) t)

e para verificar os números Motzkin

def m_count(m):
    count = sum(1 for x in ubtrees(m))
    print("Count: ", count)

>>> m_count(1)
Count:  1
>>> m_count(2)
Count:  1
>>> m_count(3)
Count:  2
>>> m_count(4)
Count:  4
>>> m_count(5)
Count:  9
>>> m_count(6)
Count:  21
>>> m_count(7)
Count:  51
>>> m_count(8)
Count:  127
>>> m_count(9)
Count:  323
>>> m_count(10)
Count:  835
>>> m_count(11)
Count:  2188
>>> m_count(12)
Count:  5798
>>> m_count(13)
Count:  15511
>>> m_count(14)
Count:  41835
>>> m_count(15)
Count:  113634

Para sair do Python interativo, use

quit()

otas sobre duplicat

A maneira como aprendi sobre os números de Motzkin foi enumerar manualmente as árvores com caneta e papel e encontrar uma duplicata usando o método de adicionar um galho unário às árvores anteriores M (N-1) e galhos binários ao M anterior anterior ( N-2) árvore

Esta árvore foi gerada duas vezes para M (5) a partir de M (4) árvores

(b (u t) (u t))

a primeira adicionando um ramo unário a

(b (u t) t)

e segundo adicionando um ramo unário a

(b t (u t))

Depois de fazer isso, tive a sequência de números 1,2,4,9,21 que usei com umOEIS search e o resultado principal foi A001006 para números Motzkin. Depois de ter a lista maior de números de Motzkin, usei o código Prolog para gerar as contagens para os valores de entrada maiores e todos concordaram. Agora você pode adicionar o OEIS à sua caixa de ferramentas de programação com um exemplo válido para demonstrar para outras pessoa

A figura maio

Se você leu até aqui, provavelmente verá que isso faz parte de um problema maior que está criando um sistema primeiro no Prolog, que pode usar a reescrita de termos para resolver expressões matemáticas de acordo com o cálculo básico, mas mostra mais importante as etapas. Portanto, isso faz parte do caminho para gerar árvores de expressão binária para serem usadas como casos de teste. O próximo passo é poder definir individualmente o número de nós unários e binários, em vez de fixá-los pelo número Motzkin. Usei apenas os números de Motzkin para verificar se estava gerando um subconjunto das combinações corretamente. Agora que tenho o padrão, posso modificá-lo para aceitar um argumento para o número de nós unários e um para os nós binários. Vejo:Como enumerar combinações usando DCGs com CLP (FD) e várias restrições

Somente quando ficar preso, farei perguntas relacionadas a isso, portanto, não espere ver todas as migalhas de pão necessária

Prolog output

?- length(Ls, N), phrase(e, Ls).
Ls = ['number(0)'],
N = 1 ;
Ls = ['[op(u),[', 'number(0)', ']]'],
N = 3 ;
Ls = ['[op(u),[', '[op(u),[', 'number(0)', ']]', ']]'],
N = 5 ;
Ls = ['[op(b),[', 'number(0)', ',', 'number(0)', ']]'],
N = 5 ;
Ls = ['[op(u),[', '[op(u),[', '[op(u),[', 'number(0)', ']]', ']]', ']]'],
N = 7 ;
Ls = ['[op(u),[', '[op(b),[', 'number(0)', ',', 'number(0)', ']]', ']]'],
N = 7 ;
Ls = ['[op(b),[', '[op(u),[', 'number(0)', ']]', ',', 'number(0)', ']]'],
N = 7 ;
Ls = ['[op(b),[', 'number(0)', ',', '[op(u),[', 'number(0)', ']]', ']]'],
N = 7 ;

?- es(S).
S = 'number(0)' ;
S = '[op(u),[number(0)]]' ;
S = '[op(u),[[op(u),[number(0)]]]]' ;
S = '[op(b),[number(0),number(0)]]' ;
S = '[op(u),[[op(u),[[op(u),[number(0)]]]]]]' ;
S = '[op(u),[[op(b),[number(0),number(0)]]]]' ;
S = '[op(b),[[op(u),[number(0)]],number(0)]]' ;
S = '[op(b),[number(0),[op(u),[number(0)]]]]' ;
S = '[op(u),[[op(u),[[op(u),[[op(u),[number(0)]]]]]]]]' ;
S = '[op(u),[[op(u),[[op(b),[number(0),number(0)]]]]]]' ;
S = '[op(u),[[op(b),[[op(u),[number(0)]],number(0)]]]]' ;
S = '[op(u),[[op(b),[number(0),[op(u),[number(0)]]]]]]' ;
S = '[op(b),[[op(u),[[op(u),[number(0)]]]],number(0)]]' ;
S = '[op(b),[[op(u),[number(0)]],[op(u),[number(0)]]]]' ;
S = '[op(b),[[op(b),[number(0),number(0)]],number(0)]]' ;
S = '[op(b),[number(0),[op(u),[[op(u),[number(0)]]]]]]' ;
S = '[op(b),[number(0),[op(b),[number(0),number(0)]]]]' ;

?- es_m(1,E).
E = 'number(n)' ;
false.

?- es_m(2,E).
E = '[op(u),[number(n)]]' ;
false.

?- es_m(3,E).
E = '[op(u),[[op(u),[number(n)]]]]' ;
E = '[op(b),[number(n),number(n)]]' ;
false.

?- es_m(4,E).
E = '[op(u),[[op(u),[[op(u),[number(n)]]]]]]' ;
E = '[op(u),[[op(b),[number(n),number(n)]]]]' ;
E = '[op(b),[[op(u),[number(n)]],number(n)]]' ;
E = '[op(b),[number(n),[op(u),[number(n)]]]]' ;
false.

?- es_m(5,E).
E = '[op(u),[[op(u),[[op(u),[[op(u),[number(n)]]]]]]]]' ;
E = '[op(u),[[op(u),[[op(b),[number(n),number(n)]]]]]]' ;
E = '[op(u),[[op(b),[[op(u),[number(n)]],number(n)]]]]' ;
E = '[op(u),[[op(b),[number(n),[op(u),[number(n)]]]]]]' ;
E = '[op(b),[[op(u),[[op(u),[number(n)]]]],number(n)]]' ;
E = '[op(b),[[op(u),[number(n)]],[op(u),[number(n)]]]]' ;
E = '[op(b),[[op(b),[number(n),number(n)]],number(n)]]' ;
E = '[op(b),[number(n),[op(u),[[op(u),[number(n)]]]]]]' ;
E = '[op(b),[number(n),[op(b),[number(n),number(n)]]]]' ;
false.