序言 - 伯爵在列表

我寫序言中的一個程序，計算的不間斷出現在列表中的第一個值的重複次數的數目。序言 - 伯爵在列表

所以給出repetitions(A,[a,a,a,a,a,b,c,a])，程序都將返回A = 5。

這是我的代碼看起來像至今：

repetitions(A,[]). 
repetitions(A,[A|T]):- repetitions(A, [_|T]), A is 1+A. 
repetitions(A,[_|T]):- repetitions(A,[A|T]).

來源

2017-03-19 tang

要知道，像'A的表達是1 + A'總是會失敗，因爲一旦它被實例化，你不能重新分配在Prolog的變量，除了通過回溯。這是因爲在邏輯上，表達式「A是1 + A」要求Prolog找到一個「A」，這樣當評估時，「A」與「1 + A」具有相同的值，這當然是不可能的。 – lurker

緊湊清晰，禮貌庫apply和yall

?- [user]. 
repetitions(A,[H|T]) :- foldl([E,(C0,H0),(C1,H1)]>>(E==H0 -> succ(C0,C1), H1=H0 ; C0=C1, H1=_), T, (1,H), (A,_)). 
|: true. 

?- repetitions(A,[a,a,a,a,a,b,c,a]). 
A = 5.

來源

2017-03-19 18:27:07 CapelliC

重複失敗（2，[a，Y]）失敗' – false

@false：好吧，應該很容易通過if_/3來糾正' – CapelliC

@false：我發現'錯誤'，在你的評論中，**強烈**主觀。也許你可以保留它的**有未定義的行爲**。當然，我不認爲它是'這個答案的情況下，但萬一，你應該更好地解釋，而不是我，但對OP ...和其他讀者以及 – CapelliC

這裏是一個關係版本：

 
repetitions(N, [First|Rest]) :- 
     phrase(repetitions_(First, 1, N), Rest). 

repetitions_(_, N, N) --> []. 
repetitions_(First, N0, N) --> [First], 
     { N1 #= N0 + 1 }, 
     repetitions_(First, N1, N). 
repetitions_(First, N, N) --> [Other], { dif(First, Other) }, ... . 

... --> [] | [_], ... .

測試用例的工作要求：

 
?- repetitions(N, [a,a,a,a,a,b,c,a]). 
N = 5 ; 
false.

而且，我們還可以在其他方向使用。

例如，什麼對一般有3件列表：

?- Ls = [A,B,C], repetitions(N, Ls). Ls = [C, C, C], A = B, B = C, N = 3 ; Ls = [B, B, C], A = B, N = 2, dif(B, C) ; Ls = [A, B, C], N = 1, dif(A, B) ; false.

又是怎麼回事所有可能的答案，通過迭代相當列舉深化：

?- length(Ls, _), repetitions(N, Ls). Ls = [_8248], N = 1 ; Ls = [_8248, _8248], N = 2 ; Ls = [_8734, _8740], N = 1, dif(_8734, _8740) ; Ls = [_8248, _8248, _8248], N = 3 ; Ls = [_8740, _8740, _8752], N = 2, dif(_8740, _8752) ; etc.

這是邏輯程序的一個主要的吸引力，它們通常可以在幾個方向使用。

請參閱dcg,prolog-dif和clpfd以獲取有關我用於實現此一般性的機制的更多信息。

我們還可以用它來回答以下問題

什麼是一個列表看起來像這樣有它的第一個元素的重複3次？

實施例：

?- repetitions(3, Ls). Ls = [_2040, _2040, _2040] ; Ls = [_2514, _2514, _2514, _2532], dif(_2514, _2532) ; Ls = [_2526, _2526, _2526, _2544, _2550], dif(_2526, _2544) ; Ls = [_2538, _2538, _2538, _2556, _2562, _2568], dif(_2538, _2556) .

這僅要求一個單一的進一步約束來上方加入到溶液中。我把這當作一個簡單的練習。

來源

2017-03-19 18:35:07 mat

終止屬性可以明顯改善。 – false

如'repetitions_mat（1，[a，a | _]）。'。 – false

通過適當的修改，解決了最後一個查詢的問題，同樣'重複（1，[a，a | _]）'會立即失敗！同樣可以用'if_/3'改進確定性！ – mat

另一種方式接近到目前爲止你做了什麼，使用CLPFD：

:- use_module(library(clpfd)). 

repetitions(N,[H|T]):-repetitions(N,[H|T],H). 

repetitions(0,[],_). 
repetitions(0,[H|_],H1):-dif(H,H1). 
repetitions(N,[H|T],H):-repetitions(N1 ,T, H), N #= N1+1.

例子：

?- repetitions(A,[a,a,a,a,a,b,c,a]). 
A = 5 ; 
false. 

?- repetitions(2,[a,Y]). 
Y = a. 

?- repetitions(N,[a,a|_]). 
N = 2 ; 
N = 2 ; 
N = 3 ; 
N = 3 ; 
N = 4 ; 
N = 4 ; 
N = 5 ; 
N = 5 ; 
N = 6 ; 
N = 6 ....and goes on

來源

2017-03-19 19:44:12 coder

不錯！請參閱測試用例張貼假的？' - 重複（1，[A，A | _]）'。理想情況下，*用'false'終止*！ – mat

@Mat，謝謝，我看到上面的測試情況，但我沒有拿出任何解決方案... – coder

把一個約束的關鍵遞歸的目標意味着它不能改善終止後。 – false

這是一個基於DCG的解決方案有所爲@墊的變化：

repetitions_II(N, [X|Cs]) :- 
    phrase((reps(X, N), no(X)), [X|Cs]). 

no(X) --> 
    ([] | [Y], {dif(X,Y)}, ...). 

reps(_X, 0) --> 
    []. 
reps(X, N0) --> 
    [X], 
    { N0 #> 0, N1 #= N0-1 }, 
    reps(X, N1).

兩個顯着的區別：

1mo）維護櫃檯沒有用處。因此，對號碼的限制可以幫助改善終止。一個完美的clpfd實現將（或者應該）以類似的效率來實現這個差異。

2do）結尾no//1實質上以純方式編碼\+[X]。

該解決方案的缺點是它仍然會產生剩餘的選擇點。爲了擺脫這些，一些手工編碼是必要的：

:- use_module(library(reif)). 

repetitions_III(N, [X|Xs]) :- 
    reps([X|Xs], X, N). 

reps([], _, 0). 
reps([X|Xs], C, N0) :- 
    N0 #>= 0, 
    if_(X = C, (N1 #= N0-1, reps(Xs, C, N1)), N0 = 0).

來源

2017-03-20 00:37:01 false

序言 - 伯爵在列表

回答

相關問題