0

我有一个序言任务。

我需要查看列表中的第一个项目，看看它的后续项目是否相同，直到它们不同，然后将列表按第一个项目及其重复项分开。例如，如果我的列表是 a、a、a、b、c，它会将其分成第一个：a、a、a。第二：b，c。

我当前的解决方案有效，但最终匹配项进入第二个列表，而不是第一个。我似乎想不出一种方法让它出现在第一个列表中。

grab([],[],[]).
grab([A,A|L],[A|L2],Rest) :- grab([A|L],L2,Rest).
grab([A|L],Init,[A|L2]) :- grab(L,Init,L2).
4

4 回答 4

4

当前两个元素不同时，您不需要递归目标。

grab([], [], []).
grab([A,A|Rest], [A|As], L2):- !, grab([A|Rest], As, L2).
grab([A|Tail], [A], Tail).
于 2014-06-07T10:19:22.753 回答
3 
grab(Xs, Ys, Zs) :-
   eqprefix(Xs, Ys, Zs).

eqprefix([],[],[]).
eqprefix([X],[],[X]).
eqprefix([X,Y|Xs], [], [X,Y|Xs]) :-
    dif(X,Y).
eqprefix([X,X|Xs], [X|Ys], Zs) :-
   eqprefix2([X|Xs], Ys, Zs).

eqprefix2([X], [X], []).
eqprefix2([X,Y|Xs], [X], [Y|Xs]) :-
    dif(X,Y).
eqprefix2([X,X|Xs], [X|Ys], Zs) :-
    eqprefix2([X|Xs], Ys, Zs).

?- eqprefix([a,a,a,b,c],Ys,Zs).
Ys = [a, a, a],
Zs = [b, c] ;
false.

?- eqprefix(Xs,[a,a,a],[b,c]).
Xs = [a, a, a, b, c] ;
false.

?- eqprefix([A,B,C,D,E],[a|Ys],[b,c]).
A = B, B = C, C = a,
D = b,
E = c,
Ys = [a, a] ;
false.

在您给出的定义中，您会得到许多不同的答案：

?- grab([a,a,a,b,c],Ys,Zs).
  Ys = [a, a], Zs = [a, b, c]
; Ys = [a],    Zs = [a, a, b, c]
; Ys = [a],    Zs = [a, a, b, c]
; Ys = [],     Zs = [a, a, a, b, c].
于 2014-06-07T14:23:56.173 回答
2

这是另一个考虑到@Sarah 所写内容的解决方案。鉴于这种用法，grab/3对于第一个或第二个参数的空列表，永远不应该成功。

grab([A], [A], []).
grab([A,B|Bs], [A], [B|Bs]) :-
   dif(A,B).
grab([A,A|Xs], [A|As], Bs) :-
   grab([A|Xs], As, Bs).

?- Xs = [A,B], grab(Xs,Ys,Zs).
  Xs = [A, B], Ys = [A],    Zs = [B], dif(A, B)
; Xs = Ys,     Ys = [B, B], Zs = [],  A = B
; false.
于 2014-06-08T10:53:54.677 回答
2

这是使用的解决方案。最有趣的是这里使用了非上下文无关的非终端。我将从一个过于笼统的尝试开始：

grab_tentative(Xs, Ys, Zs) :-
   phrase((seq(Ys),seq(Zs)), Xs).

seq([]) --> [].
seq([E|Es]) --> [E], seq(Es).

grab_tentative/3确保Xs由与Ys连接组成Zs。这太笼统了，但所有预期的解决方案都已包含在内。

?- Xs = [A,B,C], grab_tentative(Xs,Ys,Zs).
   Xs = Zs, Zs = [A, B, C], Ys = []
;  Xs = [A, B, C], Ys = [A], Zs = [B, C]
;  Xs = [A, B, C], Ys = [A, B], Zs = [C]
;  Xs = Ys, Ys = [A, B, C], Zs = []
;  false.

第一个答案说, 但是（正如@SarahYs = []已澄清的那样），应该始终是一个非空列表，因此我们可以将答案限制为非空列表：Ys

grab_tentative(Xs, Ys, Zs) :-
    Ys = [_|_] ,
   短语（（序列（Ys），序列（Zs）），Xs）。

答案Xs = [A, B, C], Ys = [A, B], Zs = [C] 和Xs = Ys, Ys = [A, B, C], Zs = [] 两者都允许A并且B是不同的。所以我们必须补充一点，它们是相同的：

grab_tentative(Xs, Ys, Zs) :-
   Ys = [A|_]，
   短语(( all_seq(=(A),Ys) ,seq(Zs)), Xs)。

all_seq(_, []) --> []。
all_seq(C_1, [C|Cs]) -->
   [C]，
   {呼叫（C_1，C）}，
   all_seq(C_1, Cs)。

现在，答案已经好一点了：

?- Xs = [A,B,C], grab_tentative(Xs,Ys,Zs).
   Xs = [A, B, C], Ys = [A], Zs = [B, C]
;  Xs = [B, B, C], A = B, Ys = [B, B], Zs = [C]
;  Xs = Ys, Ys = [C, C, C], A = B, B = C, Zs = []
;  false.

第一个答案包括A = B. 所以，它真的应该包含dif(A,B). 为此，我们需要引入这样的上下文。这是执行此操作的方法。请注意，or_end//1就像[]//0，除了它确保了一些额外的条件。

grab_final(Xs, Ys, Zs) :-
   Ys = [A|_]，
   短语((all_seq(=(A),Ys), or_end(dif(A)) , seq(Zs)), Xs)。

or_end(C_1) -->
  调用（cond_or_end（C_1））。% 谓词接口

cond_or_end(_C_1, [], [])。
cond_or_end(C_1, [E|Es], [E|Es]) :-

现在，答案如预期：

?- Xs = [A,B,C], grab_final(Xs, Ys, Zs).
   Xs = [A, B, C], Ys = [A], Zs = [B, C], dif(A, B)
;  Xs = [B, B, C], A = B, Ys = [B, B], Zs = [C], dif(B, C)
;  Xs = Ys, Ys = [C, C, C], A = B, B = C, Zs = []
;  false.
于 2014-06-08T13:53:20.007 回答