計數的連續出現在序言

你好我試圖在Prolog的一個程序，給定一個列表它計算每個連續的元素出現在名單如下：計數的連續出現在序言

count(1,[1,1,1,2,2,2,3,1,1],0,X)

結果將是X=[ [1,3],[2,3],[3,1][1,2] ] 又名每個子列表是[element,occurrences]

在我的情況下，我相信有基本情況有問題，但我無法解決它。你可以幫我嗎？

%append an element to a list 
append([ ],Y,Y). 
append([X|Xs],Ys,[X|Zs]):-append(Xs,Ys,Zs). 

%c is the counter beginning with 0 
count(_,[],_,[]). 
count(X,[X],C,[L]):-count(X,[],C,[L|[X,C]]). 

%increase counter 
count(X,[X|Tail],C,L):-Z is C+1,count(X,Tail,Z,L). 
count(X,[Head|Tail],C,[L]):-append(L,[X,C],NL),count(Head,Tail,1,NL).

來源

2014-11-20 JmRag

我至少可以看到一個問題就在這裏：'[L | [X，C]]'會產生一個普通列表。 L是頭（單個元素），[X，C]是尾部列表。更新：哦，你已經編輯它.. – 2014-11-20 21:16:28

@EugeneSh。實際上，當我試圖將我的代碼簡化爲基本問題而不是完全實現它時，它包含了更多與問題無關的謂詞。 – JmRag 2014-11-20 21:20:52

在你的'append'基本情況下，你需要'append（[]，Y，[Y]）。'如果我明白它的意圖。 – 2014-11-20 21:26:56

這是另一個嘗試做ru n長度編碼，基於clpfd！

 
:- use_module(library(clpfd)).

基於if_/3和(=)/3，我們定義list_rle/2：

 
list_rle([],[]). 
list_rle([X|Xs],[N*X|Ps]) :- 
    list_count_prev_runs(Xs,N,X,Ps). 

list_count_prev_runs(Es,N,X,Ps) :- 
    N #> 0, 
    N #= N0+1, 
    list_count_prev_runs_(Es,N0,X,Ps). 

list_count_prev_runs_([],0,_,[]). 
list_count_prev_runs_([E|Es],N,X,Ps0) :- 
    if_(X=E, 
     list_count_prev_runs(Es,N,X,Ps0), 
     (N = 0, Ps0 = [M*E|Ps], list_count_prev_runs(Es,M,E,Ps))).

示例查詢：

編碼/解碼＃1

 
?- list_rle([a,a,b,c,c,c,d,e,e],Ys). 
Ys = [2*a,1*b,3*c,1*d,2*e]. 

?- list_rle(Xs,[2*a,1*b,3*c,1*d,2*e]). 
    Xs = [a,a,b,c,c,c,d,e,e] 
; false.

編碼/解碼＃2

 
?- dif(A,B),dif(B,C),dif(C,D),dif(D,E), list_rle([A,A,B,C,C,C,D,E,E],Ys). 
Ys = [2*A,1*B,3*C,1*D,2*E], dif(A,B), dif(B,C), dif(C,D), dif(D,E). 

?- list_rle(Xs,[2*A,1*B,3*C,1*D,2*E]). 
    Xs = [A,A,B,C,C,C,D,E,E], dif(A,B), dif(B,C), dif(C,D), dif(D,E) 
; false.

怎麼樣一些更一般的東西？

 
?- list_rle([A,B,C,D],Xs). 
    Xs = [4*A   ],  A=B ,  B=C ,  C=D 
; Xs = [3*A,  1*D],  A=B ,  B=C , dif(C,D) 
; Xs = [2*A, 2*C ],  A=B , dif(B,C),  C=D 
; Xs = [2*A, 1*C,1*D],  A=B , dif(B,C), dif(C,D) 
; Xs = [1*A,3*B  ], dif(A,B),  B=C ,  C=D 
; Xs = [1*A,2*B, 1*D], dif(A,B),  B=C , dif(C,D) 
; Xs = [1*A,1*B,2*C ], dif(A,B), dif(B,C),  C=D 
; Xs = [1*A,1*B,1*C,1*D], dif(A,B), dif(B,C), dif(C,D).

來源

2015-10-16 22:18:22 repeat

所以理論上它對'？ - list_rle（Xs，[2 * a，1 * b，3 * c，1 * d，2 * e]）來說仍然會更好。 Xs = [a，a，b，c，c，c，d，e，e] ;假。「是確定性的權利？並沒有一個選擇點？ – user27815 2015-10-18 12:34:56

@ user27815。它會。但我們必須達到平衡並確定優先順序：正確性>多功能性>效率。 – repeat 2015-10-18 13:05:28

爲什麼你要聲明兩個列表之間的關係與一個謂詞有4個參數？讓我們試着一步一步來。

空列表給出了一個空列表，計數被遞增的元件，否則，開始計數...

count([],[]). 
count([X|T],[[X,C1]|R]) :- count(T,[[X,C]|R]), !, C1 is C+1. 
count([X|T],[[X,1]|R]) :- count(T,R). 

?- count([1,1,1,2,2,2,3,1,1],R). 
R = [[1, 3], [2, 3], [3, 1], [1, 2]].

那麼容易（當然，假設X = [[1,3]，[2 ，3]，[1,3] [1,2]這是一個錯字...）

來源

2014-11-20 21:40:27 CapelliC

哇你的回答讓我看起來像個白癡。我對prolog還不是很熟悉，而且我的想法和我在編程方面一樣。 Thx很多爲您的答案和解釋！是的，你大膽指出的是一個錯字，我編輯的問題是正確的。 – JmRag 2014-11-20 21:53:13

另一種解決方案（尾遞歸）是這樣的：

run_length_encode(Xs , Ys) :- % to find the run length encoding of a list , 
    rle(Xs , 1 , Ys) .   % - just invoke the helper 

rle([]  , _ , [] ) .  % the run length encoding of the empty list is the empty list 
rle([A]  , N , [X:N]) .  % A list of length 1 terminates the run: move the run length to the result 
rle([A,A|Xs] , N , Ys ) :- % otherwise, if the run is still going 
    N1 is N+1 ,      % - increment the count, 
    rle([A|Xs] , N1 , Ys)   % - and recurse down 
    .        % 
rle([A,B|Xs] , N , [A:N|Ys]) :- % otherwise, if the run has ended 
    A \= B ,      % - we have a break 
    rle([B|Xs] , 1 , Ys)   % - add the completed run length to the result and recurse down 
    .        %

來源

2014-11-21 01:06:49

我們能夠解決您的問題一個d保存logical-purity！

下面讓我們Xs爲[1,1,1,2,2,2,3,1,1]，您在問題中使用的列表。

首先，我們映射到Xs名單列表Yss使得Yss每個列表Ys只包含來自Xs採取相同的元素。我們通過使用元謂詞splitlistIfAdj/3亦隨物化的不平等謂詞dif/3：

?- Xs = [1,1,1,2,2,2,3,1,1], splitlistIfAdj(dif,Xs,Yss). 
Xs = [ 1,1,1, 2,2,2, 3, 1,1 ], 
Yss = [[1,1,1],[2,2,2],[3],[1,1]].

二，我們映射列表Yss到Zss名單。 Zss中的每個項目的格式爲[Element,Amount]。綜觀上述查詢的答案，我們可以看到，我們需要做的就是地圖[1,1,1]到[1,3]，[2,2,2]到[2,3]，[3]到[3,1]，並[1,1]到[1,2]。 run_pair/2正是這麼做的：

run_pair(Ys,[Element,Amount]) :- 
    Ys = [Element|_], 
    length(Ys,Amount).

讓我們用run_pair/2到Yss每個項目地圖，與元謂詞maplist/3的幫助：

 
?- Yss = [[1,1,1],[2,2,2],[3],[1,1]], maplist(run_pair,Yss,Zss). 
Yss = [[1,1,1],[2,2,2],[3] ,[1,1]], 
Zss = [[1,3], [2,3], [3,1],[1,2]].

完成！時間把它放在一起：

count(Xs,Zss) :- 
    splitlistIfAdj(dif,Xs,Yss), 
    maplist(run_pair,Yss,Zss).

讓我們看看上面的查詢仍然有效:)

?- count([1,1,1,2,2,2,3,1,1],Zss). 
Zss = [[1,3],[2,3],[3,1],[1,2]].  % succeeds deterministically

由於count/2實現是單調，我們得到與工作時邏輯聽起來答案甚至非基礎條款。讓我們看看在行動！

?- Xs = [A,B,C,D], count(Xs,Zss). 
Xs = [D,D,D,D],  A=B,  B=C ,  C=D , Zss = [     [D,4]] ; 
Xs = [C,C,C,D],  A=B,  B=C , dif(C,D), Zss = [   [C,3],[D,1]] ; 
Xs = [B,B,D,D],  A=B, dif(B,C),  C=D , Zss = [  [B,2],  [D,2]] ; 
Xs = [B,B,C,D],  A=B, dif(B,C), dif(C,D), Zss = [  [B,2],[C,1],[D,1]] ; 
Xs = [A,D,D,D], dif(A,B),  B=C ,  C=D , Zss = [[A,1],   [D,3]] ; 
Xs = [A,C,C,D], dif(A,B),  B=C , dif(C,D), Zss = [[A,1],  [C,2],[D,1]] ; 
Xs = [A,B,D,D], dif(A,B), dif(B,C),  C=D , Zss = [[A,1],[B,1],  [D,2]] ; 
Xs = [A,B,C,D], dif(A,B), dif(B,C), dif(C,D), Zss = [[A,1],[B,1],[C,1],[D,1]].

來源

2015-05-16 18:58:04 repeat

如果我們忽略的「是」的使用，我們可以有這樣一個解決方案：

precondition(Clause):- 
    Clause =.. [_|ARGS], 
    (maplist(var,ARGS) -> true; Clause). 

count([], []). 

count([X], [(X,1)]) :- !. 

count([H|Q], [(H,1),(HR,NR)|QR]) :- 
    count(Q, [(HR,NR)|QR]), 
    H \= HR, 
    !. 

count([H|Q], [(H,NR)|QR]) :- 
    precondition(succ(N,NR)), 
    count(Q, [(H,N)|QR]), 
    succ(N,NR).

，不僅可以讓平時查詢：

[debug] ?- count([1,1,1,2,2,2,3,1,1],R). 
R = [ (1, 3), (2, 3), (3, 1), (1, 2)].

而且相反的一個：

[debug] ?- count(X, [ (1, 3), (2, 3), (3, 1), (1, 2)]). 
X = [1, 1, 1, 2, 2, 2, 3, 1, 1].

來源

2015-05-21 14:13:08

計數的連續出現在序言

回答

相關問題