3

我在返回 P-99 问题 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 = [] .

我想在最后一条规则的末尾应该有额外的行以某种方式将结果绑定到输入，但我不知道该怎么做。

4

7 回答 7

2

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

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
| ?-
于 2013-09-18T01:29:51.093 回答
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最后使用的情况下预先添加，但我的后兜里没有。

于 2013-09-17T17:11:15.840 回答
2

这是使您的代码工作所需的最小修改：添加一个“仅返回”变量，以将内部工作附加的结果“浮现”到顶层：

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 是关于关系，而不是函数），但通常是一种有用的、简单的技术。

高温高压

于 2013-09-18T08:13:09.407 回答
2

以下是您如何以逻辑上纯粹的方式做到这一点：将元谓词与的具体变体splitlistIfAdj/3结合使用。让我们现在做一些查询！dif/3

?- 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

与不纯代码不同，实现是单调的，可以与非基本术语一起使用：

?- 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).
于 2015-05-05T11:43:24.463 回答
1

如果你使用 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

于 2013-09-18T07:36:22.890 回答
0

我认为这样的事情应该有效：

%=============================
% 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
于 2013-09-18T00:41:07.960 回答
-1 
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
于 2019-02-19T05:15:33.850 回答