按字典顺序创建值对 0 到 n-1 的列表

Question

我正在做一个程序，结果是一对值 [X,Y]，按字典顺序在 0 和 N-1 之间

我现在有这个：

pairs(N,R) :-
   pairsHelp(N,R,0,0).

pairsHelp(N,[],N,N) :- !.
pairsHelp(N,[],N,0) :- !.
pairsHelp(N,[[X,Y]|List],X,Y) :-
    Y is N-1,
    X < N,
    X1 is X + 1,
    pairsHelp(N,List,X1,0).
pairsHelp(N,[[X,Y]|List],X,Y) :-
    Y < N,
    Y1 is Y + 1,
    pairsHelp(N,List,X,Y1).

我在第一次迭代中得到了我想要的结果，但 Prolog 继续进行，然后给了我第二个答案。

?-pairs(2,R).
R = [[0,0],[0,1],[1,0],[1,1]] ;
false.

我不要第二个答案（false），只想要第一个。我希望它在找到答案后停止。有什么想法吗？

Answer 1

请记住，有一种更更简单的方法来获得您想要的东西。如果确实X和Y都应该是整数，用between/3来枚举整数（这里的"lexicographical"和自然数的顺序是一样的：0,1,2,....这是如果第三个参数是变量，between/3 将枚举可能的解决方案的顺序）：

pairs(N, R) :-
    succ(N0, N),
    bagof(P, pair(N0, P), R).

pair(N0, X-Y) :-
    between(0, N0, X),
    between(0, N0, Y).

然后：

?- pairs(2, R).
R = [0-0, 0-1, 1-0, 1-1].

?- pairs(3, R).
R = [0-0, 0-1, 0-2, 1-0, 1-1, 1-2, 2-0, 2-1, ... - ...].

我使用传统的 Prolog 方式来表示一对，X-Y（规范形式：-(X, Y)）而不是 [X,Y]（规范形式：.(X, .(Y, []))） .

这个程序的优点是您可以轻松地重新编写它以与您选择的另一个 "alphabet" 一起使用。

?- between(0, Upper, X).

在语义上等同于：

x(0).
x(1).
% ...
x(Upper).

?- x(X).

例如，如果我们有一个由 b、a 和 c 组成的字母表（按此顺序！）：

foo(b).
foo(a).
foo(c).

foo_pairs(Ps) :-
    bagof(X-Y, ( foo(X), foo(Y) ), Ps).

然后：

?- foo_pairs(R).
R = [b-b, b-a, b-c, a-b, a-a, a-c, c-b, c-a, ... - ...].

foo/1 的子句顺序定义了字母表的顺序。连词 foo(X), foo(Y) 与对中 X-Y 的顺序一起定义了对在列表中的顺序。尝试编写例如 bagof(X-Y, ( foo(Y), foo(X) ), Ps) 以查看 Ps.

中对的顺序是什么

Answer 2

使用dcg in combination with lambda!

?- use_module(library(lambda)).

结合meta-predicate init0/3和 ("cross product") 只需写：

?- init0(=,3,Xs), phrase(xproduct(\X^Y^phrase([X-Y]),Xs),Pss).
Xs = [0,1,2], Pss = [0-0,0-1,0-2,1-0,1-1,1-2,2-0,2-1,2-2].

稍微更一般的东西怎么样？ N 的其他值呢？

?- init0(=,N,Xs), phrase(xproduct(\X^Y^phrase([X-Y]),Xs),Pss).
  N = 0, Xs = [],          Pss = []
; N = 1, Xs = [0],         Pss = [0-0]
; N = 2, Xs = [0,1],       Pss = [0-0,0-1,
                                  1-0,1-1]
; N = 3, Xs = [0,1,2],     Pss = [0-0,0-1,0-2,
                                  1-0,1-1,1-2,
                                  2-0,2-1,2-2]
; N = 4, Xs = [0,1,2,3],   Pss = [0-0,0-1,0-2,0-3,
                                  1-0,1-1,1-2,1-3,
                                  2-0,2-1,2-2,2-3,
                                  3-0,3-1,3-2,3-3] 
; N = 5, Xs = [0,1,2,3,4], Pss = [0-0,0-1,0-2,0-3,0-4,
                                  1-0,1-1,1-2,1-3,1-4,
                                  2-0,2-1,2-2,2-3,2-4,
                                  3-0,3-1,3-2,3-3,3-4,
                                  4-0,4-1,4-2,4-3,4-4]
...

它也适用于其他术语吗？订单呢？考虑@Boris 在 :

中使用的案例

?- phrase(xproduct(\X^Y^phrase([X-Y]),[b,a,c]),Pss).
Pss = [b-b,b-a,b-c,a-b,a-a,a-c,c-b,c-a,c-c].  % succeeds deterministically

按字典顺序创建值对 0 到 n-1 的列表

Create list of pair of values 0 to n-1 in lexicographical order

list

prolog