查找Prolog列表元素的組合/子列表

-1

我試圖編寫一個函數，它將生成通過刪除1或2個元素（包括拆分列表）而形成的列表元素的組合。查找Prolog列表元素的組合/子列表

例如：

[b,b,b]

可能成爲

[b,b] 
[b] 
[[b],[b]]

我可以使用下面的謂詞生成前兩個：

permute([_|T],T). 
permute([_|[_|T]],T).

但第三被證明更加困難。我可以使用append將列表分成兩部分，但我不知道如何將其與已有的部分結合起來。

我正在使用SWI-Prolog。

（雖然標記爲家庭作業，這是一個更大的任務的一部分，並且是我堅持的時刻）

來源

2011-03-05 dig412

這些不是排列組合，所以請不要給他們打電話。 – 2011-03-05 17:16:42

他們有正確的名詞嗎？（變化/子列表？） – dig412 2011-03-05 17:24:08

從您的描述來看，子列表似乎是一個更合適的術語。 – 2011-03-05 17:40:40

謂詞

permute([_|T],T). 
permute([_|[_|T]],T).

會更恰當地命名爲tail_or_tail_of_tail。你注意到它只能刪除第一個或前兩個元素嗎？如果你想採取任何兩個元素，使用類似

take_out_one_or_two(L, R) :- select(_, L, R). 
take_out_one_or_two(L, R) :- select(_, L, L1), select(_, L1, R).

你說得對，拆分可以用append/3完成。你（很奇怪）要求由

strange_predicate(L, R) :- take_out_one_or_two(L, R). 
strange_predicate(L, [X,Y]) :- take_out_one_or_two(L, L1), append(X, Y, L1).

會見如果您不想空列表在搜索結果中，有

strange_predicate(L, [X,Y]) :- 
    take_out_one_or_two(L, L1), 
    X = [_|_], 
    Y = [_|_], 
    append(X, Y, L1).

更換第二條（我實在想不出一個名字）

來源

2011-03-05 17:50:39

謝謝！這是Kayles的遊戲，其中列表元素表示瓶子可以以1或2組的形式被撞倒，因此奇怪的要求是，一組將被分成兩半。由於所有元素都是相同的，從開始或結束中刪除元素沒有任何區別，但感謝更新後的謂詞。 – dig412 2011-03-05 17:57:18

@ dig412：如果所有元素都相同，那麼你不需要列表。一個整數計數器或一對'Elem + Count'（例如'b + 3'）就足夠了。 – 2011-03-05 17:59:47

這可以工作，它肯定會簡化一些列表操作。我仍然習慣於Prolog，這是一種非常不同的編程方式。 – dig412 2011-03-05 18:38:37

以Kayles的遊戲爲例，我們的應用程序建議一個經濟的狀態表示將是一個有序整數的有序列表，每個數字代表一串連續的瓶子。

我說的是有序的，因爲遊戲的狀態在這些值的任何排列下是等價的。

可能的舉動因此將包括選擇一個條目並將其減少一到兩個零個，一個或兩個較小的條目。這些較小的條目（如果有的話）應該插入遊戲狀態列表的新「尾部」中的適當位置。

遊戲移動的更大表示的一個構建塊是決定連續的一串X瓶可以減少多少種方式。因此，我們可以與要求入手：

bowls(X,[ ]) :- 
    (0 is X - 1 ; 0 is X-2). 
bowls(X,[W]) :- 
    (W is X - 1 ; W is X-2), 
    W > 0. 
bowls(X,[Y,Z]) :- 
    (W is X - 1 ; W is X-2), 
    W > 1, 
    bowlsplits(W,Y,Z).

它留給讀者來實現bowlsplits/3以這樣一種方式，它生產的所有可能性，Y + Z = W與Y >= Z > 0。

請注意，對於這樣的表示，我們應該跳過任何等於列表中以下條目的條目來避免重複結果，因爲兩個相同的條目會產生相同的可能結果。

kayles([X],R) :- bowls(X,R). 
kayles([X,Y|T],R) :- 
    X > Y, 
    bowls(X,L), 
    inSort(L,[Y|T],R). 
kayles([X,X|T],[X|L]) :- 
    kayles([X|T],L).

它也留給讀者來實現inSort/3沿插入的是融合在其前兩個參數的有序列表爲有序列表結合第三個參數的行排序。

請注意，kayles/2是尾遞歸但非確定性。

來源

2011-03-08 16:52:47 hardmath

查找Prolog列表元素的組合/子列表

回答

相關問題