在Prolog中将列表元素的连续重复项打包成子列表

Question

我在返回P-99: Ninety-Nine Prolog Problems的第9道题答案时遇到了问题：

将列表元素的连续重复项打包成子列表。如果一个列表包含重复元素，则应将它们放置在单独的子列表中。

样例查询及预期结果：

?- pack([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
X = [[a,a,a,a],[b],[c,c],[a,a],[d],[e,e,e,e]].

我能够将元素打包进子列表，但我不知道如何返回答案。

这是我的代码：

pack(X,Y) :- pack(X,[],Y).
pack([H,H|T],Acc,X) :- pack([H|T],[H|Acc],X).
pack([H,H1|T], Acc, X) :- 
    H\=H1, 
    Acc1=[H|Acc],
    append(X, [Acc1], X1),
    pack([H1|T],[],X1).
pack([H], Acc, X) :- 
    Acc1=[H|Acc],
    append(X, [Acc1], X1).

以下是在跟踪模式下运行的查询：

?- trace, pack([a,a,a,a,b,c,c],X).
   Call: (6) pack([a, a, a, a, b, c, c], _G986) ? creep
   Call: (7) pack([a, a, a, a, b, c, c], [], _G986) ? creep
   Call: (8) pack([a, a, a, b, c, c], [a], _G986) ? creep
   Call: (9) pack([a, a, b, c, c], [a, a], _G986) ? creep
   Call: (10) pack([a, b, c, c], [a, a, a], _G986) ? creep
   Call: (11) a\=b ? creep
   Exit: (11) a\=b ? creep
   Call: (11) _G1100=[a, a, a, a] ? creep
   Exit: (11) [a, a, a, a]=[a, a, a, a] ? creep
   Call: (11) lists:append(_G986, [[a, a, a, a]], _G1105) ? creep
   Exit: (11) lists:append([], [[a, a, a, a]], [[a, a, a, a]]) ? creep
   Call: (11) pack([b, c, c], [], [[a, a, a, a]]) ? creep
   Call: (12) b\=c ? creep
   Exit: (12) b\=c ? creep
   Call: (12) _G1109=[b] ? creep
   Exit: (12) [b]=[b] ? creep
   Call: (12) lists:append([[a, a, a, a]], [[b]], _G1114) ? creep
   Exit: (12) lists:append([[a, a, a, a]], [[b]], [[a, a, a, a], [b]]) ? creep
   Call: (12) pack([c, c], [], [[a, a, a, a], [b]]) ? creep
   Call: (13) pack([c], [c], [[a, a, a, a], [b]]) ? creep
   Call: (14) _G1127=[c, c] ? creep
   Exit: (14) [c, c]=[c, c] ? creep
   Call: (14) lists:append([[a, a, a, a], [b]], [[c, c]], _G1132) ? creep
   Exit: (14) lists:append([[a, a, a, a], [b]], [[c, c]], [[a, a, a, a], [b], [c, c]]) ? creep
   Exit: (13) pack([c], [c], [[a, a, a, a], [b]]) ? creep
   Exit: (12) pack([c, c], [], [[a, a, a, a], [b]]) ? creep
   Exit: (11) pack([b, c, c], [], [[a, a, a, a]]) ? creep
   Exit: (10) pack([a, b, c, c], [a, a, a], []) ? creep
   Exit: (9) pack([a, a, b, c, c], [a, a], []) ? creep
   Exit: (8) pack([a, a, a, b, c, c], [a], []) ? creep
   Exit: (7) pack([a, a, a, a, b, c, c], [], []) ? creep
   Exit: (6) pack([a, a, a, a, b, c, c], []) ? creep
X = [] .

我想最后一条规则应该有额外的行来将结果与输入绑定起来，但我不知道如何做到。

- Sgt. Pepper

Answer 1

这是如何以逻辑纯粹的方式完成它的方法：使用元谓词splitlistIfAdj/3与dif/3结合，后者是prolog-dif的一种实现。让我们立即进行一些查询！

?- Xs = [a], splitlistIfAdj(dif,Xs,Pss).
Xs  = [ a ],
Pss = [[a]].                                    % succeeds deterministically

?- Xs = [a,a,a,a,b,c,c], splitlistIfAdj(dif,Xs,Pss).
Xs  = [ a,a,a,a,  b,  c,c ],
Pss = [[a,a,a,a],[b],[c,c]].                    % succeeds deterministically

?- Xs = [a,a,a,a,b,c,c,a,a,d,e,e,e,e], splitlistIfAdj(dif,Xs,Pss).
Xs  = [ a,a,a,a,  b,  c,c,  a,a,  d,  e,e,e,e ],
Pss = [[a,a,a,a],[b],[c,c],[a,a],[d],[e,e,e,e]].% succeeds deterministically

与不纯净的代码不同，该实现是单调递增的，可以与非ground项一起使用：

？- Xs = [A,B]，splitlistIfAdj(dif,Xs,Pss)，A=1，B=2。
Xs = [1,2]，A = 1，B = 2，Pss = [[1]，[2]]。
？- Xs = [A,B]，A=1，B=2，splitlistIfAdj(dif,Xs,Pss)。％逻辑上等价
Xs = [1,2]，A = 1，B = 2，Pss = [[1]，[2]]。

请注意，像以下更加通用的查询也会给出逻辑上正确的答案：

?- Xs = [A,B,C,D], splitlistIfAdj(dif,Xs,Pss).
Xs = [D,D,D,D], Pss = [[D,D,D,D]],           A=B ,     B=C ,     C=D  ;
Xs = [C,C,C,D], Pss = [[C,C,C],[D]],         A=B ,     B=C , dif(C,D) ;
Xs = [B,B,D,D], Pss = [[B,B],[D,D]],         A=B , dif(B,C),     C=D  ;
Xs = [B,B,C,D], Pss = [[B,B],[C],[D]],       A=B , dif(B,C), dif(C,D) ;
Xs = [A,D,D,D], Pss = [[A],[D,D,D]],     dif(A,B),     B=C ,     C=D  ;
Xs = [A,C,C,D], Pss = [[A],[C,C],[D]],   dif(A,B),     B=C , dif(C,D) ;
Xs = [A,B,D,D], Pss = [[A],[B],[D,D]],   dif(A,B), dif(B,C),     C=D  ;
Xs = [A,B,C,D], Pss = [[A],[B],[C],[D]], dif(A,B), dif(B,C), dif(C,D).

- repeat

Answer 2

首先，您会收到有关X1的单例变量警告：

pack([H], Acc, X) :- 
    Acc1=[H|Acc],
    append(X, [Acc1], X1).

这整个规则简化为以下内容：

pack([H], Acc, X) :- append(X, [[H|Acc]], _).

我确定这不是你想要的，但是看到你提供的内容，我不确定你到底想要什么。首先，我不会使用append/3来解决这个问题。你的解决方案实际上生成了一个不同值的列表，这告诉我在某个地方出现了严重的错误。

?- pack([a, a, a, a, b, c, c], X).
X = [] ;
X = [_G704] ;
X = [_G704, _G710] ;
X = [_G704, _G710, _G716] ;
X = [_G704, _G710, _G716, _G722] a

我希望我能看到问题，因为在追踪中我看到你正在正确地构建结果。有更深入了解的人可能会提供修复您的拼写错误的方法。

无论如何，这是我想到的：

pack([X|Unpacked], Packed) :- pack(Unpacked, [[X]], Packed).

pack([H|T], [[H|Acc]|Rest], Packed) :- pack(T, [[H,H|Acc]|Rest], Packed).
pack([X|T], [[Y|Acc]|Rest], Packed) :-
    X \= Y,
    pack(T, [[X],[Y|Acc]|Rest], Packed).
pack([], RPacked, Packed) :- reverse(RPacked, Packed).

事实上，差异列表解决方案可以允许在不使用append/3或在末尾使用reverse/2的情况下进行前置操作，但我没有这样的解决方案。

- Daniel Lyons

Answer 3

我认为这个会起作用。我使用了一个“累加器”来收集重复成员子列表。

pack([], []).
pack(L, Pack) :-
    pack(L, [], Pack).

pack([X], FrontPack, [[X|FrontPack]]).
pack([X,X|T], FrontPack, Pack) :-
    pack([X|T], [X|FrontPack], Pack).
pack([X,Y|T], FrontPack, [[X|FrontPack]|Pack]) :-
    X \= Y,
    pack([Y|T], [], Pack).

结果：

| ?- pack([a],X).

X = [[a]] ? ;

no.
| ?- pack([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).

X = [[a,a,a,a],[b],[c,c],[a,a],[d],[e,e,e,e]] ? ;

no
| ?-

- lurker

Answer 4

这是使您的代码工作所需的最小修改：添加一个“return only”变量，将内部工作附加到顶层以“合并”结果。

pack(X,Y) :- pack(X,[],_,Y).
pack([H,H|T],Acc,X,R) :- pack([H|T],[H|Acc],X,R).

pack([H,H1|T], Acc, X,R) :-
    H\=H1,
    Acc1=[H|Acc],
    append(X, [Acc1], X1),
    pack([H1|T],[],X1,R).

pack([H], Acc, X,R) :-
    Acc1=[H|Acc],
    append(X, [Acc1], X1),
    R = X1.

测试：

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

正如您所见，有许多替代算法可用：这是我的算法，我尝试使它尽可能简单：

pack(L, P) :- pack(L, [], P).

pack([X|Xs], R, P) :-
    add_pack(X, R, R1), pack(Xs, R1, P).
pack([], R, P) :-
    reverse(R, P).

add_pack(X, [[X|Xs]|R], [[X,X|Xs]|R]).
add_pack(X, [R|Rs], [[X],R|Rs]).
add_pack(X, [], [[X]]).

它的行为最类似于“朴素插入排序”：取前面的元素并将其放在正确的位置。为避免附加元素，我使用了一个累加器，在最后被反转（与这里大多数其他答案相同）。

编辑 我猜，阅读其他答案，有人发现你的代码难以理解。原因可能是您混合了“输入/输出”参数。作为一种风格选择，Prologgers通常坚持“先输入，后输出”。这并不总是有意义的（毕竟，Prolog是关于关系的，而不是函数），但仍然经常是一种有用、简单的技术。

希望对你有帮助。

- CapelliC

Answer 5

如果您使用SWI-Prolog，配合module(library(lambda))和foldl，您可以编写如下代码：

:- use_module(library(lambda)).

pack(L, PL) :-
L = [A | B],
foldl(\X^Y^Z^(Y = [LY | RY],
          (   member(X, LY)
          ->  Z = [[X | LY]|RY]
          ;   Z = [[X]| [LY | RY]])),
      B, [[A]], RPL),
reverse(RPL, PL).

可以在这里找到lambda.pl模块: http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl

- joel76

---

对于SWI-Prolog用户，lambda可作为包使用：?- pack_install(lambda). - CapelliC

Answer 6

应该可以像这样工作，我想：

%=============================
% pack/2: The public interface
%=============================
pack( []     , []     ) .                   % packing an empty list yields the empty list
pack( [X|Xs] , [Y|Ys] ) :-                  % packing a non-empty list consists of
  construct_run( Xs , [X] , Run , Tail ) ,  % - building a run of length 1 or more from the prefix of the list
  simplify_run( Run , Y ) ,                 % - simplfying it for the special case of a run of length 1
  pack( Tail , Ys )                         % - and then recursively packing whatever is left.
  .                                         % Easy!

%--------------------------
% private helper predicates
%--------------------------

%
% construct_run/4
%
construct_run( []     , Run    , Run    , []     ) .  % the run is complete if the source list is exhausted
construct_run( [X|Xs] , [R|Rs] , [R|Rs] , [X|Xs] ) :- % the run is complete if the head of the source list differs
  T \= R                                              %   from what's already in the run
  .                                                   %
construct_run( [X|Xs] , [R|Rs] , Run    , Tail   ) :  % otherwise, 
  T =  R ,                                            % - if the head of the source list matches what's already in the run,
  construct_run( Xs , [T,R|Rs] , Run , Tail )         % - we prepend it to the run and recurse down.
  .                                                   %

%
% simplify_run/2 - deal with the special case of run length 1
%
simplify_run( [A]     , A       ) . % run length = 1
simplify_run( [A,B|C] , [A,B|C] ) . % run length > 1

- Nicholas Carey

Answer 7

class find:
    def enter_list(self): #function defined to create comma seperated list
        input_element=raw_input('Enter comma seperated elements -')
        mylist=[ x for x in input_element.split(',')]
        return mylist

    def get_sublist(self,x):
        prev=""  #prev flag generated to check previous element match or not 
        return_list=[]  #return_list created to store final output
        flag=0 #as first element dont have prev element to check for match
        for i in range(len(x)):
            if x[i]!=prev: #if no prev match then create new sublist
                if flag==0: #for first element
                    sorted_list=[] #sorted_list is used to store sublist
                    sorted_list.append(x[i]) 
                    prev=x[i]
                else:
                    return_list.append(sorted_list)
                    sorted_list=[]
                    sorted_list.append(x[i])
                    prev=x[i]
            elif x[i]==prev: #if match with prev append to sublist
                sorted_list.append(x[i])
                prev=x[i]
                flag=1
            if i==len(x)-1: #block to append last sublist to list
                return_list.append(sorted_list)
        return return_list
a=find()
create_list=a.enter_list()
print "Entered list : ",create_list
print a.get_sublist(create_list) #print output by providing normal list

- yugandhara

---

请在您的代码中加入一些解释。仅仅提供代码而没有任何解释是没有用的。 - Partho63