先行词中的条件顺序导致堆栈溢出

Question

作为一个简单的练习，我编写了自己的排列。

此堆栈溢出：

without(_, [], []).
without(A, [A|T], T).
without(A, [H|T], [H|G]) :- without(A, T, G).

my_permutation([], []).
my_permutation([H|T], P) :- member(H, P), without(H, P, Pp), my_permutation(T, Pp).

这可以部分工作，但在提供一些解决方案空间后仍然会出现堆栈溢出：

without(_, [], []).
without(A, [A|T], T).
without(A, [H|T], [H|G]) :- without(A, T, G).

my_permutation([], []).
my_permutation([H|T], P) :- my_permutation(T, Pp), member(H, P), without(H, P, Pp).

这也会导致堆栈溢出：

without(A, [A|T], T).
without(A, [H|T], [H|G]) :- without(A, T, G).

my_permutation([], []).
my_permutation([H|T], P) :- without(H, P, Pp), my_permutation(T, Pp).

但这非常有效：

without(A, [A|T], T).
without(A, [H|T], [H|G]) :- without(A, T, G).

my_permutation([], []).
my_permutation([H|T], P) :- my_permutation(T, Pp), without(H, P, Pp).

任何人都可以帮我理解为什么吗？

Answer 1

问题出在这部分：

without(H, P, Pp)

P 和 Pp 都未实例化，因此

without

愉快地进入无限循环，根据 T 和 G 变量，为它们提供越来越长的长度。

解决办法是更换：

my_permutation([H|T], P) :- without(H, P, Pp), my_permutation(T, Pp).

...使得列表长度受到限制，导致终止。

这就足够了（尽管使用

same_length

会使速度变慢）：

my_permutation([H|T], P) :-
    same_length([H|T], P),
    without(H, P, Pp),
    my_permutation(T, Pp).

或者，更好（使用 E 作为“Element”的简称，即列表的元素）：

my_permutation([H|T], [E|P]) :- without(E, [H|T], R), my_permutation(R, P).

这清楚地将

my_permutation

的两个参数绑定为相同的长度，并将实例化列表 (

[H|T]

) 传递给

without

。