4

是否有任何 prolog 实现能够枚举可数无限结果的所有元素？

让我们考虑枚举所有自然数对。如果我们按 {(0,0), (0,1), (1,0), (0,2), (1,1), (2,0), ...} 的顺序枚举对，我们可以枚举所有对。但是，如果我们按照以下 GNU prolog 程序的顺序 {(0,0), (0,1), (0,2), (0,3) ...} 枚举对，我们永远不会达到诸如 ( 1,1)。

% cat nats.pl
nat(0).
nat(X1) :- nat(X), X1 is X + 1.

pair_of_nats(X, Y) :- nat(X), nat(Y).
% prolog
GNU Prolog 1.3.0
By Daniel Diaz
Copyright (C) 1999-2007 Daniel Diaz
| ?- ['nats.pl'].
compiling /home/egi/prolog/nats.pl for byte code...
/home/egi/prolog/nats.pl compiled, 4 lines read - 762 bytes written, 9 ms

yes
| ?- pair_of_nats(X,Y).

X = 0
Y = 0 ? ;

X = 0
Y = 1 ? ;

X = 0
Y = 2 ? ;

X = 0
Y = 3 ?
4

4 回答 4

3

我首先认为 CappeliCs 解决方案很好。但是再看看 lurkers
CLP(FD) 解决方案，我认为以下是一个完整的 Prolog 解决方案：

?- between(0, inf, X), between(0, X, A), B is X-A.

再见

PS：这是在 SWI-Prolog 中运行的示例：

Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.1.33)
Copyright (c) 1990-2015 University of Amsterdam, VU Amsterdam
?- [user].
pair((A, B)) :- 
   between(0, inf, X), 
   between(0, X, A), 
   B is X-A.

?- pair(P).
P = (0, 0) ;
P = (0, 1) ;
P = (1, 0) ;
P = (0, 2) ;
P = (1, 1) ;
P = (2, 0) ;
...
于 2015-08-22T17:16:59.530 回答
2

使用您拥有的这个定义不容易做到这一点的原因nat/1是，您想要的顺序需要搜索既不是深度优先也不是广度优先的证明树。@CapelliC 的答案是广度优先搜索。@lurker 的答案为您提供了您所追求的答案。

如果出于某种原因您不想使用 CLPFD，这里是纯 Prolog 中的解决方案：

pairs(A, B) :-
    pairs_1(0, 0, A, B).

pairs_1(A, B, A, B).
pairs_1(A, B, RA, RB) :-
    (   succ(B1, B)
    ->  succ(A, A1),
        pairs_1(A1, B1, RA, RB)
    ;   succ(A, B1),
        pairs_1(0, B1, RA, RB)
    ).

它简单地描述了如何通过有理数矩阵“移动”以枚举所有整数对。

于 2015-02-10T13:04:54.483 回答
1

您可以使用 CLPFD（有限域上的约束逻辑编程）来生成所有对：

nat(0).
nat(X1) :- nat(X), X1 is X + 1.

pairs((A, B)) :-
    nat(X),
    A + B #= X,
    fd_labeling([A,B]).

这大致遵循经典康托尔证明中使用的有理数矩阵的遍历，即有理数是可数的（在每个对角线上运行相同的方向而不是交替），导致：

| ?- pairs(P).

P = (0,0) ? ;

P = (0,1) ? ;

P = (1,0) ? ;

P = (0,2) ? ;

P = (1,1) ? ;

P = (2,0) ? ;

P = (0,3) ? ;

P = (1,2) ? ;

P = (2,1) ? ;

P = (3,0) ? ;

P = (0,4) ? ;
...
于 2015-02-10T12:04:57.550 回答
0

我建议使用具有可选有限上限值的生成器，例如 between/3，而不是 nat/1，以便能够使“内部级别”饱和。例如

?- between(0,inf,A),between(0,A,B).
A = B, B = 0 ;
A = 1,
B = 0 ;
A = B, B = 1 ;
A = 2,
B = 0 ;
A = 2,
B = 1 ;
A = B, B = 2 ;
A = 3,
B = 0
....

GNU Prolog 不允许between(0,inf,A)，所以可以添加current_prolog_flag(max_integer,Z)和使用Z而不是inf.

于 2015-02-10T07:12:48.103 回答