序言 - 列表中的序列

我们想构建一个谓词，获得一个列表L和一个数字N，如果N是列表L的最长序列的长度，则该谓词为true。例如：序言 - 列表中的序列

?- ls([1,2,2,4,4,4,2,3,2],3). 
    true. 

?- ls([1,2,3,2,3,2,1,7,8],3). 
    false.

为此，我建 -

head([X|S],X). % head of the list 
ls([H|T],N) :- head(T,X),H=X, NN is N-1 , ls(T,NN) . % if the head equal to his following 
ls(_,0) :- !. % get seq in length N 
ls([H|T],N) :- head(T,X) , not(H=X) ,ls(T,N). % if the head doesn't equal to his following

的概念很简单 - 检查头等于他的下面，如果是的话，继续与尾部和递减N。

我检查了我的代码，它工作得很好（忽略案件N = 1） -

ls([1,2,2,4,4,4,2,3,2],3). 
true ; 
false .

但true答案不是有限的，后面也有更多的答案，我怎么能让它返回有限回答？

来源

2013-02-28 URL87

序言方面，你有几个问题。一个是你的谓词只在两个参数都被实例化时才起作用，这对Prolog来说是令人失望的。另一种是你的风格 - head/2并没有真正添加任何东西而不是[H|T]。我也认为这个算法有根本的缺陷。我不认为你可以确定没有保留不变的猜测长度副本，在列表尾部不存在更长的序列。换句话说，@Zakum指出的第二件事，我不认为会有一个简单的解决方案。

这就是我将如何接近这个问题。

max(X, Y, X) :- X >= Y. 
max(X, Y, Y) :- Y > X.

现在大部分的工作sequence_length/2的不被委托给一个循环，除了空列表的基本情况：一是为获得最大的两个值的辅助谓词

sequence_length([], 0). 
sequence_length([X|Xs], Length) :- 
    once(sequence_length_loop(X, Xs, 1, Length)).

的致电once/1确保我们只能得到一个答案。这将防止谓词有用地生成序列列表，同时也使谓词具有确定性，这是您所期望的。（它与放置很好的剪辑具有相同的效果）。

回路的基本情况：蓄能器复制到输出参数：

sequence_length_loop(_, [], Length, Length).

电感情况＃1：我们有相同的值的另一副本。递增累加器并再次发生。

sequence_length_loop(X, [X|Xs], Acc, Length) :- 
    succ(Acc, Acc1), 
    sequence_length_loop(X, Xs, Acc1, Length).

归纳案例2：我们有不同的价值。计算列表中其余部分的序列长度;如果它大于我们的累加器，请使用它;否则，请使用累加器。

sequence_length_loop(X, [Y|Xs], Acc, Length) :- 
    X \= Y, 
    sequence_length([Y|Xs], LengthRemaining), 
    max(Acc, LengthRemaining, Length).

这就是我将如何处理这个问题。我不知道它是否对你有用，但我希望你能从中收集一些信息。

来源

2013-02-28 07:16:07

谢谢！这非常有用。 – URL87 2013-02-28 11:45:52

@Daniel_Lyons：如果你能解释一下我会很高兴，正如你所说'once'确保我们只得到1个答案，但是如果我们忽略这个'once'并保留 - sequence_length_loop（X，Xs， 1，长度）'，可以检查哪些更多的检查会得到更多结果？这里是我们只发送给'sequence_length_loop'的实例化参数'（X，Xs，1，Length）'...... – URL87 2013-02-28 14:14:11

@ URL87我们得到一个没有'once'的虚假选择点，就像你在原来的那样。我在这里选择了“一次”，因为我觉得在每个其他目标之后引入一个切换更加整洁，它比循环目标之后的切换更清楚地表达目的。 – 2013-02-28 14:58:44

如何为最后一条规则添加一个中断？

head([X|S],X). % head of the list 
ls([H|T],N) :- head(T,X),H=X, NN is N-1 , ls(T,NN) . % if the head equal to his following 
ls(_,0) :- !.           % get seq in length N 
ls([H|T],N) :- head(T,X) , not(H=X) ,ls(T,N),!.   % if the head doesn't equal to his following

适合我，尽管我不是Prolog的专家。

//编辑： btw。尝试

14 ?- ls([1,2,2,4,4,4,2,3,2],2). 
true ; 
false.

对我来说是虚假的，没有检查N是否是最长的序列。还是我的要求错了？

来源

2013-02-28 00:55:37 Zakum

您的代码正在检查列表中是否存在至少一个指定长度的元素序列。您需要更多参数才能在访问列表时保持搜索状态：

ls([E|Es], L) :- ls(E, 1, Es, L). 

ls(X, N, [Y|Ys], L) :- 
    ( X = Y 
    -> M is N+1, 
    ls(X, M, Ys, L) 
    ; ls(Y, 1, Ys, M), 
    (M > N -> L = M ; L = N) 
). 
ls(_, N, [], N).

来源

2013-02-28 08:01:12 CapelliC

序言 - 列表中的序列

回答

相关问题