pseudocodigo - Enumerando árboles binarios en Prolog

profundidad de un arbol en prolog

Question

Estoy tratando de crear reglas Prolog para enumerar ''árboles binarios'' en forma de lista en Prolog. Soy nuevo en Prolog.

Un árbol con 0 nodos es una lista vacía:

[]

Un árbol con 1 nodo es:

[[],[]]

Un árbol con 2 nodos tiene 2 posibilidades:

[[],[[],[]]]
[[[],[]],[]]

y así.

Aquí están mis reglas:

bintree(0,[]).
bintree(1,[[],[]]).
bintree(N,[Lc,Rc]) :-
N > 1,
bintree(N1,Lc),
bintree(N2,Rc),
N1 >= 0,
N2 >= 0,
N3 is N1+N2+1,
N==N3.

Las consultas para 0 y 1 obviamente funcionan. Para N = 2, imprime una de las posibilidades, pero da un error después de ingresar el punto y coma para obtener la otra posibilidad. Las consultas para N> 2 dan un error directamente. El error es siempre el mismo:

ERROR: >/2: Arguments are not sufficiently instantiated

Leí sobre este error en algunos sitios web, pero no puedo entender qué está causando este error aquí.

Gracias por su ayuda con anticipación.

Answer 1

El uso de la biblioteca CLPFD ayudará a dar una solución limpia para generar los tamaños. Entonces no necesitas un integer/1 predicado wonky (;)), que puede ser problemático:

:- use_module(library(clpfd)).
bintree(0,[]).
bintree(1,[[],[]]).
bintree(N, [L, R]) :-
N #> 1,
N #= N1 + N2 + 1,
N1 #>= 0, N2 #>= 0,
bintree(N1, L), bintree(N2, R).

O más simple (gracias a la sugerencia de @ repeat):

bintree(0,[]).
bintree(N, [L, R]) :-
N #> 0,
N #= N1 + N2 + 1,
N1 #>= 0, N2 #>= 0,
bintree(N1, L), bintree(N2, R).
?- bintree(4, L).
L = [[], [[], [[], [[], []]]]] ;
L = [[], [[], [[[], []], []]]] ;
L = [[], [[[], []], [[], []]]] ;
L = [[], [[[], [[], []]], []]] ;
L = [[], [[[[], []], []], []]] ;
L = [[[], []], [[], [[], []]]] ;
L = [[[], []], [[[], []], []]] ;
L = [[[], [[], []]], [[], []]] ;
L = [[[], [[], [[], []]]], []] ;
L = [[[], [[[], []], []]], []] ;
L = [[[[], []], []], [[], []]] ;
L = [[[[], []], [[], []]], []] ;
L = [[[[], [[], []]], []], []] ;
L = [[[[[], []], []], []], []] ;
false.
?-

CLPFD es una forma agradable y declarativa de expresar restricciones numéricas.

Answer 2

Sé que publiqué esta pregunta hace un año, pero logré resolverla más tarde sin utilizar ninguna biblioteca. Aquí está mi solución:

%binary tree generator
bintree(0,[]). %0 nodes - empty list
bintree(1,[[],[]]). %1 node - list containing 2 empty lists
bintree(N,[Cl,Cr]) :-
N>=2, %check only if at least 2 nodes
between(0,N,Nl), %let Nl be in [0,N]
between(0,N,Nr), %similarly for Nr
Ns is Nl+Nr+1, %total no. of nodes should add up correctly
N==Ns, %so check for that
bintree(Nl,Cl), %children should also be valid binary trees
bintree(Nr,Cr).