prolog - 这个排列算法是如何工作的

Question

ar([],[]).
ar([p(_,_)|L],L1):-ar(L,L2),L1=L2.
ar([p(X,Y)|L],L1):-ar(L,L2),L1=[p(X,Y)|L2].

(p代表点，坐标为X和Y)

请帮助我理解结果是如何构造的，特别是 L1 获得新值的部分，谢谢!

Answer 1

谓词的定义 ar/2 的行为类似于 powerset函数，是以下语法的变体(其中 X 仅限于 p/2 的术语):

% clause 1: base case
ps([], []).

% clause 2: omit the element X
ps([_X|Y], Z) :-
    ps(Y, Z). 

% clause 3: keep the element X
ps([X|Y], [X|Z]) :-
    ps(Y, Z).

谓词ps/2(和您的ar/2)基本上回溯将第一个参数中列表的所有子列表绑定(bind)到第二个参数的列表。它通过第二个和第三个子句所代表的选择来实现这一点:在构造新列表时省略或保留列表元素。

考虑 Prolog 在执行目标时会做什么 ps([a,b],L):

• ps([_|[b]], Z) :- ps([b], Z). (通过第 2 条，删除 a)。
  • ps([b|[]], Z) :- ps([], Z). (通过第 2 条，删除 b；注意 [b] = [b|[]])。
    • ps([], Z) 绑定(bind) Z = [](通过子句 1，给出解决方案 1)。
  • ps([b|[]], [b|Z]) :- ps([], Z). (通过第 3 条，保留 b) 。
    • ps([], Z) 绑定(bind) Z = [](通过子句 1，给出解决方案 2)。
• ps([_|[b]], [a|Z]) :- ps([b], Z). (通过第 3 条，保留 a)。
  • ps([b|[]], Z) :- ps([], Z). (通过第 2 条，删除 b)。
    • ps([], Z) 绑定(bind) Z = [](通过子句 1，给出解决方案 3)。
  • ps([b|[]], [b|Z]) :- ps([], Z). (通过第 3 条，保留 b) 。
    • ps([], Z) 绑定(bind) Z = [](通过子句 1，给出解决方案 4)。

触及子句 1 的“基本情况”的每个最深级别都会返回调用堆栈。每种情况都会导致以下结果:

1. 同时删除 a 和 b:[]
2. 删除a，保留b:[b]
3. 保留a，删除b:[a]
4. 同时保留 a 和 b:[a,b]

因此，我们可以回溯生成[]、[b]、[a]和[a,b] ，即[a,b]的四个子列表。