序言中只有两个元素的排序列表

Question

先看下面的例子：

?-  fp(X,[b,a,b]).

错误好的，因为第二个参数必须是双元素排序列表。（在我的程序中，我假设 a<b）

?-fp(X,[a,b,b]).
X = [a, b, b] ;
X = [b, a, b] ;
X = [b, b, a] ;
false.

是的，这是正确的结果。
然而，对于

?-fp ([b,a,b], X)
X = [a,b,b].

是的，这是预期的结果。
但是，如果

?-fp ([b,a,b], X)
X = [a,b,b];

这是循环....

有没有办法处理这个循环？我想了很久，但没有成功。你能帮帮我吗？

fp(L, F) :-
   fp(L, [], [], F).

fp([], AccA, AccB, F):-
   append(AccA, AccB, F), !.
fp([a|L], AccA, AccB, F) :-
   append([a|AccA], _, F),
   fp(L, [a|AccA], AccB, F).
fp([b|L], AccA, AccB, F) :-
   append(_, [b|AccB], F),
   fp(L, AccA, [b|AccB], F).

Answer 1

问题在于，对具有如此多变量的 append/3 的查询会产生几乎无限数量的解决方案供您尝试。限制它的一种方法是确保列表长度相同。正如@mat 所说，你摆脱了削减。

fp(L, F) :-
   same_length(L, F),
   fp(L, [], [], F).

fp([], AccA, AccB, F):-
   append(AccA, AccB, F).
fp([a|L], AccA, AccB, F) :-
   append([a|AccA], _, F),
   fp(L, [a|AccA], AccB, F).
fp([b|L], AccA, AccB, F) :-
   append(_, [b|AccB], F),

same_length/2 已经在 SWI Prolog 中定义，但有一个简单的实现：

same_length([], []).
same_length([_|T1], [_|T2]) :- same_length(T1, T2).

| ?- fp(X, [a,b,b,b]).

X = [a,b,b,b] ? a

X = [b,a,b,b]

X = [b,b,a,b]

X = [b,b,b,a]

(1 ms) no
| ?- fp([a,b,a], X).

X = [a,a,b] ? a

no
| ?-

序言中只有两个元素的排序列表

Sorting list with only two elements in prolog

prolog

failure-slice