1

首先看下面的例子： 

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

false 好的，因为第二个参数必须是双元素排序列表。（在我的程序中，我假设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).
4

1 回答 1

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
| ?-
于 2016-05-18T14:13:29.163 回答