4

刚刚被介绍给prolog，试图完成一些简单的练习，但我一直在这个问题上卡住了。我正在尝试编写一个输出输入列表的所有子列表的程序，其中每个子列表的长度> 1，并且不能扩展到更大的子列表。它还将输出子列表列表中的起始位置。所以一个样本输出将是

| ?- plateau([a,a,b,2,2,2,a+1,a+1,s(1,2)], I, Len).
    I = 1,
    Len = 2 ? ;
    I = 4,
    Len = 3 ? ;
    I = 7,
    Len = 2 ? ;
    no

我仍然对整个声明式的事情感到很困惑，并且在切换命令式模式时遇到了很多麻烦。我在想我希望我的程序做类似的事情

program([H|T],I,L):-
    T = [H1|T1] %split the tail
    ([H] = [H1] -> Count is Count+1, program(T,I,Count) 
     %if First element = second element, recurse with new values
    ; length(T,Spot), 
      %get the spot where you are in the list, so we know where sublist starts
      program(T,Spot,L) %run again, from tail, since sublist didn't have another  element?
program([],I,L). %terminate when entire list has been run through?

所以这行不通，从我可以说的几个原因来看。我没有重置“计数”，所以它可能会将所有子列表的值加起来？有没有办法解决这个问题？我的基本情况也可能不是我想要的——我只是不确定它应该是什么？我可能也错过了其他东西......非常感谢任何帮助！：） 谢谢！

4

5 回答 5

7

您的程序将许多不同的问题组合到一个谓词中。让我们试着把它们分开一点。另外，我假设您正在搜索包含相同元素的两个或多个元素的最大子列表。

让我们从您想要的近似值开始：识别子列表。不要担心这太宽泛了，我们稍后会完善它。为此，我将使用 DCG。非终结符seq//1描述任意序列。

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

这是一个非常有用的非终端！

?- 短语((seq(Prefix),seq(Sublist),seq(Postfix)),
      [a,a,b,2,2,2,a+1,a+1,s(1,2)])。
前缀 = 子列表，子列表 = []，
后缀 = [a,a,b,2,2,2,a+1,a+1,s(1,2)] ;
前缀 = [],
子列表 = "a" ,
后缀 = [a,b,2,2,2,a+1,a+1,s(1,2)] ...

这两个答案都不是预期的，我们只想要长度为 2 或更多的子列表，因此我们必须稍微限制该定义。说，通过要求Sublist至少应该包含两个元素。那就是Sublist = [_,_|_]。

?- 子列表 = [_,_|_],
   短语（（序列（前缀），序列（子列表），序列（后缀）），
      [a,a,b,2,2,2,a+1,a+1,s(1,2)])。
子列表 = "aa",
前缀 = [],
后缀 = [b,2,2,2,a+1,a+1,s(1,2)] ;
子列表 = "aab" ,
前缀 = [],
后缀 = [2,2,2,a+1,a+1,s(1,2)] ...

第一个答案显示了我们正在搜索的子列表。但第二个仍然不正确：子列表的所有元素都应该相等。最简单的方法是使用maplist/2：

?- maplist(=(_),Es)。
Es = [] ;
Es = [_G221] ;
Es = [_G221,_G221] ;
Es = [_G221,_G221,_G221]

有几个地方我们可以说明这个要求。我会把它放在尽可能早的地方：

?- 子列表 = [_,_|_],
        短语（（序列（前缀），
                 seq(子列表),{maplist(=(_),子列表)},
                 序列（后缀）），
           [a,a,b,2,2,2,a+1,a+1,s(1,2)])。
子列表 = "aa",
前缀 = [],
后缀 = [b,2,2,2,a+1,a+1,s(1,2)] ;
子列表 = [2,2]，
前缀 = "aab",
后缀 = [2,a+1,a+1,s(1,2)] ;
子列表 = [2,2,2],
前缀 = "aab",
后缀 = [a+1,a+1,s(1,2)] ;
子列表 = [2,2]，
前缀 = [a,a,b,2],
后缀 = [a+1,a+1,s(1,2)] ;
子列表 = [a+1,a+1],
前缀 = [a,a,b,2,2,2],
后缀 = [s(1,2)] ;
错误的。

所以现在，所有子列表都包含相同的元素。唉，我们得到了两个[2,2]和[2,2,2]作为子列表。我们只想要最大的子列表。那么我们如何描述最大子列表是什么？

一种方法是查看我们的子列表的前面：我们的子列表中不能有完全相同的元素。因此，要么前面没有任何东西（epsilon），要么以与我们不同的元素结束的序列。

difel(_E,[]).
difel(E, Es) :- dif(E,F), phrase((seq(_), [F]), Es).

?- 子列表 = [_,_|_],
   短语（（序列（前缀），{difel（E，前缀）}，
            seq(子列表),{maplist(=(E),子列表)},
            序列（后缀）），
      [a,a,b,2,2,2,a+1,a+1,s(1,2)])。
子列表 = "aa",
前缀 = [],
E = 一个，
后缀 = [b,2,2,2,a+1,a+1,s(1,2)] ;
子列表 = [2,2]，
前缀 = "aab",
E = 2,
后缀 = [2,a+1,a+1,s(1,2)] ;
子列表 = [2,2,2],
前缀 = "aab",
E = 2,
后缀 = [a+1,a+1,s(1,2)] ;
子列表 = [a+1,a+1],
前缀 = [a,a,b,2,2,2],
E = a+1,
后缀 = [s(1,2)] ;
错误的。

少一个错误答案。最后还有一个潜伏在身边。

?- 子列表 = [_,_|_],
   短语（（序列（前缀），{difel（E，前缀）}，
            seq(子列表),{maplist(=(E),子列表)},
            ( [] | [F],{dif(E,F)},seq(_) ) ),
      [a,a,b,2,2,2,a+1,a+1,s(1,2)])。
子列表 = "aa",
前缀 = [],
E = 一个，
F = b;
子列表 = [2,2,2],
前缀 = "aab",
E = 2,
F = a+1 ;
子列表 = [a+1,a+1],
前缀 = [a,a,b,2,2,2],
E = a+1,
F = s(1,2) ;
错误的。

这并不是你想要的：你只是想要长度。为此，添加length([_|Prefix],I), length(Sublist,Len).

所以这是最终的定义：

高原（Xs，I，Len）：-
   子列表 = [_,_|_],
   短语（（序列（前缀），{difel（E，前缀）}，
            seq(子列表),{maplist(=(E),子列表)},
            ( [] | [F],{dif(E,F)},seq(_) ) ),
      Xs),
   长度([_|前缀],I),
   长度（子列表，Len）。
于 2012-03-13T14:43:05.470 回答
2

这里有很多复杂的答案。考虑一下不使用 DCG 或许多内置插件的这个（对于初学者来说可能更简单）：

plateau([X|Xs], I, L) :-
    plateau(Xs, 1-1-X, I, L).

plateau([X1|Xs], I0-L0-X0, I, L) :-
    X0 == X1, !,
    NL0 is L0 + 1,
    plateau(Xs, I0-NL0-X0, I, L).

plateau(_, I-L-_, I, L) :-
    L > 1.

plateau([X|Xs], I0-L0-_, I, L) :-
    NI is I0 + L0,
    plateau(Xs, NI-1-X, I, L).

第一个子句将累积(index)- (length)-(sublist element)元组的调用设置为一个术语。

length如果下一个列表相同，则下一个子句递增element（注意索引未更改）。

仅当测试子列表元素 run 是否被破坏（因为 cut ）时第二个子句失败时才调用第三个子句，并且如果 run 是 则返回!解决方案。length> 1

最后一个子句使 Prolog 能够回溯并从上次运行开始重新开始搜索。

编辑： gusbro 的解决方案实际上非常接近这个... +1。

于 2012-03-15T22:12:31.443 回答
1

我尝试使用 nth1/3 内置，但更麻烦的是让它工作......无论如何，这里是另一个实现：

plateau(L, I, Len) :-
    plateau(L, 1, I, Len).
plateau(L, P, I, Len) :-
    nth1(P, L, E),
    skipseq(P, L, E, J),
    (   J > P,
        Len is J - P + 1,
        I is P
    ;   Q is J + 1,
        plateau(L, Q, I, Len)
    ).

% get the index J of last element E (after I)
skipseq(I, L, E, J) :-
    T is I + 1,
    nth1(T, L, E),
    !, skipseq(T, L, E, J).
skipseq(I, _, _, I).

测试：

[debug]  ?- plateau([a,x,x,x,u,u,h,w],I,N).
I = 2,
N = 3 ;
I = 5,
N = 2 ;
false.
于 2012-03-13T17:39:30.317 回答
1

你可以这样做：

plateau([Item|Tail], I, Len):-
  plateau(Tail, 1, Item, 1, I, Len).

plateau(List, From, NItem, Len, From, Len):-
  (List=[Item|_] -> (Item\=NItem;var(Item)); List = []),
  Len > 1.
plateau([Item|Tail], IFrom, Item, ILen, From, Len):-
  MLen is ILen + 1,
  plateau(Tail, IFrom, Item, MLen, From, Len).
plateau([Item|Tail], IFrom, OItem, ILen, From, Len):-
  OItem \= Item,
  NFrom is IFrom + ILen,
  plateau(Tail, NFrom, Item, 1, From, Len).

高原/6 的第一个子句处理子列表的终止。可能是该项目与您正在查找的项目不同，或者您已到达列表的末尾。在这种情况下，我们仅在当前长度大于 1 时继续。

第二个子句处理我们仍然匹配列表中的元素的情况下的递归步骤。它只是将一个添加到当前子列表的计数器并进行递归。

最后一个子句处理在列表中找到一个新的（不同的）项目的情况，只是重置计数器并进行递归。

于 2012-03-13T14:32:12.153 回答
1

这是简单明了的。我们从 1 开始计数；高原是相等元素的最大子序列，长度至少为 2；我们按照清单进行。把它写下来：

plateau(L,I,N):- plateau(L,1,I,N).                     % count from 1

plateau([A,A|B],I1,I,N):- !, more_elts(A,B,2,K,C),     % two equals, or more
    (I is I1, N is K ; plateau(C,I1+K,I,N)).
plateau([_|B],I1,I,N):- plateau(B,I1+1,I,N).           % move along the list

more_elts(A,[A|B],I,K,C):- !, more_elts(A,B,I+1,K,C).
more_elts(_,B,I,I,B).

更新：假设输入列表的所有元素都是nonvar/1. 在这里将非实例化变量作为输入列表的元素会使“子列表”的概念变得棘手和模糊。例如，什么是子列表[a,X,b,b]？[a,a]两者[b,b,b] 都可以是同一输入列表的子列表吗？（这使我想起了可观察到的自旋值，状态叠加等的值。在sokuza-kanren.scm 中（在此处找到该链接））

于 2012-03-16T10:50:13.440 回答