使用給定公式的可能的列表置換

Question

我想讓我的頭繞在Prolog的列表中。要做到這一點，我正在嘗試創造一種遊戲。你傳遞一個可以重複的數字1-9的列表，列表可以是任意長度。規則是從第一個元素（e）開始，你只能移動到e + 2或e + 3，直到最後。目標是「登陸」最高的數字。本質上它有點像跳房子。我遇到的問題是確定路徑的所有可能的排列。到目前爲止，我有以下幾點。

paths([], []). %empty list returns empty list 
paths([X], [X]). %list with one element returns that one element 
paths([X1, X2], [X1]). %list with 2 elements returns the first element 
paths([X1, X2, X3], [X1,X3]). %list with three elements returns the first and third element 
paths() :- % the recursive case for a list with 4+ elements 

使用將是一個列表：[1,2,3,4,5,6,8,7,9,3,6,5,7,8,9] 我需要確定使用約所提到的規則的所有可能路徑。我希望清單在序言:(

任何邏輯的指導，將不勝感激索引

Answer 1

我認爲這是有原因的，以避免indexing：。簡單如果你分解你的問題，也許你可以開始寫步/ 3謂詞像

step([_,X|T],X,T). 
step([_,_,X|T],X,T). 

然後

paths([],[]). 
paths(L,[X|Xs]) :- step(L,X,T), paths(T,Xs). 

注：我不很瞭解你的遊戲，操場上的一些示例並歡迎解決方案。

Answer 2

的要求並不完全清楚，但似乎是：

• 的第二個參數必須具有相同的第一元素作爲 第一個參數（你的第一個「廣場「跳」 「總是首先，使用 您跳房子metaphore）

• 你不需要第一個列表的最後一個元素是第二列表的 最後一個元素（你是不是要求您‘土地 上’最後一個「方塊」）。

• 空列表成功與一個空表結果（而不僅僅是沒有一個空的名單上 - 這是另一種有效的方法）。

然後這可以如下實施。由於它們是由遞歸子句和簡單的基本情況處理的，因此不需要許多顯式的2元素和3元素列表情況。

path([], []). 
path([X], [X]). 
path([X,_|T], [X|R]) :- % hop over 1 element 
    path(T, R). 
path([X,_,_|T], [X|R]) :- % hop over 2 elements 
    path(T, R). 

舉個簡單的例子：

| ?- path([1,2,3,4,5,6], R). 

R = [1,3,5] ? ; 

R = [1,3,6] ? ; 

R = [1,4,6] ? ; 

R = [1,4] 

yes 

如果我沒有你的要求完全正確的，你應該能夠調整此根據自己的需要，因爲它顯示瞭如何處理遞歸情況。這聽起來像是你正試圖優化你的啤酒花的價值，我也將作爲一個練習離開。

這也可以用DCG（明確條款語法）做

path([]) --> []. 
path([X]) --> [X]. 
path([X|T]) --> ([X,_] | [X,_,_]), path(T). 

這將是行使：

| ?- phrase(path(R), [1,2,3,4,5,6]). 

R = [1,3,5] ? ; 

R = [1,3,6] ? ; 

R = [1,4,6] ? ; 

R = [1,4] ? ; 

(1 ms) no 
| ?- 

---

在所採取的最後一步額外的要求，光必須是列表中的一個，這裏是 path/2謂詞的更新版本：

path([], []). 
path([X], [X]). 
path([X,_], [X]). 
path([X,_,Y|T], [X|R]) :- % hop over 1 element 
    path([Y|T], R). 
path([X,_,_,Y|T], [X|R]) :- % hop over 2 elements 
    path([Y|T], R). 

Answer 3

%passing in a list and return all possible paths using K+2 or K+3 with K being the first element of the list. 
%empty list returns empty list 
%list with one element returns that one element 
%list with 2 elements returns the first element 
%list with three elements returns the first and third element 
%list with four/four+ elements needs to be called recursively, prefix them with the first element and append them together 
%RL means ReturnList 
%FL means FinalList 
%List is the appended list containing all the paths 
paths([], []). 
paths([X], [[X]]). 
paths([X1, X2], [[X1]]). 
paths([X1, X2, X3], [[X1,X3]]). 
paths([X1, X2, X3, X4 | T], List) :- 
    paths([X3,X4|T], RL), paths([X4|T], RL2), 
    prefix_all(X1, RL, FL1), prefix_all(X1, RL2, FL2), 
    append(FL1, FL2, List). 

所以如果用列表[1,2,3,4,5]運行時會產生如下：

| ?- paths([1,2,3,4,5],X). 

X = [[1,3,5],[1,4]] ? ; 
no