Prolog中的集合（列表）的幂集

Question

我有下一个谓词，它将从列表中生成所有子集：

candidate([],[]).
candidate([H|T],[H|R]):-
    candidate(T,R).
candidate([_|T],R):-
    candidate(T,R).

有人可以帮助我了解它是如何工作的吗？看起来很短，但背后的循环感觉很复杂。

Answer 1

很容易看出 {} 的唯一子集是 {}。

candidate([], []).

假设您要生成集合 S = {a,b,c} 的所有子集。

然后，可以从S中移除一个元素（比如元素a），得到集合S-{a} = {b,c}.

通过归纳假设，可以生成{b,c}的所有子集，即 {}、{b}、{c}、{b,c}。这是由目标 candidate(T, R).

完成的

由于 {b,c} 的每个子集也是 {a,b,c} 的子集，您可以得出结论 S = {a,b,c} 的子集是：

{}, {b}, {c}, {b,c} (candidate([_|T],R) :- candidate(T,R)),

以及这些相同的子集与集合 {a} 连接，即：

{a}, {a,b}, {a,c}, {a,b,c} (candidate([H|T],[H|R]) :- candidate(T,R)).

通过改变两个递归规则的顺序，您可以更清楚地看到这一点。

candidate([], []).
candidate([_|T], R):- candidate(T, R).     % does not include first element
candidate([H|T], [H|R]):- candidate(T,R).  % do include first element

结果：

?- candidate([a,b,c],S).
S = [] ;
S = [c] ;
S = [b] ;
S = [b, c] ;
S = [a] ;
S = [a, c] ;
S = [a, b] ;
S = [a, b, c].

Prolog中的集合（列表）的幂集

Powerset o a set(list) in Prolog

prolog