在 Prolog 中枚举二叉树
Enumerating binary trees in Prolog
我正在尝试创建 Prolog 规则以在 Prolog 中以列表形式枚举 'binary trees'。我是 Prolog 的新手。
具有 0 个节点的树是一个空列表:
[]
具有 1 个节点的树是:
[[],[]]
一棵有 2 个节点的树有 2 种可能性:
[[],[[],[]]]
[[[],[]],[]]
等等。
这是我的规则:
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.
查询 0 和 1 显然有效。对于 N=2,它会打印其中一种可能性,但在我输入分号以获取另一种可能性后会出现错误。
查询N>2直接报错。错误总是一样的:
ERROR: >/2: Arguments are not sufficiently instantiated
我在一些网站上看到了这个错误,但我无法弄清楚是什么导致了这个错误。
提前感谢您的帮助。
使用 CLPFD 库将有助于提供一个干净的解决方案来生成尺寸。那么你不需要一个不稳定的 (;)) integer/1
谓词,这可能会有问题:
:- 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).
或更简单(感谢@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 是表达数值约束的一种很好的声明方式。
我知道我在一年前发布了这个问题,但我后来在没有使用任何库的情况下设法解决了它。这是我的解决方案:
%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).
我正在尝试创建 Prolog 规则以在 Prolog 中以列表形式枚举 'binary trees'。我是 Prolog 的新手。
具有 0 个节点的树是一个空列表:
[]
具有 1 个节点的树是:
[[],[]]
一棵有 2 个节点的树有 2 种可能性:
[[],[[],[]]]
[[[],[]],[]]
等等。
这是我的规则:
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.
查询 0 和 1 显然有效。对于 N=2,它会打印其中一种可能性,但在我输入分号以获取另一种可能性后会出现错误。 查询N>2直接报错。错误总是一样的:
ERROR: >/2: Arguments are not sufficiently instantiated
我在一些网站上看到了这个错误,但我无法弄清楚是什么导致了这个错误。
提前感谢您的帮助。
使用 CLPFD 库将有助于提供一个干净的解决方案来生成尺寸。那么你不需要一个不稳定的 (;)) integer/1
谓词,这可能会有问题:
:- 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).
或更简单(感谢@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 是表达数值约束的一种很好的声明方式。
我知道我在一年前发布了这个问题,但我后来在没有使用任何库的情况下设法解决了它。这是我的解决方案:
%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).