序言 - 在N部分中劃分列表

Question

我想寫一個將列表劃分爲N部分的謂詞。 這是我到目前爲止。

partition(1, List, List). 
partition(N, List, [X,Y|Rest]):- 
    chop(List, X, Y), 
    member(NextToChop, [X,Y]), %Choose one of the new parts to chop further. 
    NewN is N-1, 
    partition(NewN, NextToChop, Rest). 

chop(List, _, _):- 
    length(List, Length), 
    Length < 2, %You can't chop something that doesn't have at least 2 elements 
    fail,!. 
chop(List, Deel1, Deel2):- 
    append(Deel1, Deel2, List), 
    Deel1 \= [], 
    Deel2 \= []. 

這個想法是繼續將列表的部分切成兩個其他部分，直到我有N件。 我有這種方法效果平平：

?- partition(2, [1,2,3,4], List). 
List = [[1], [2, 3, 4], 1] ; 
List = [[1], [2, 3, 4], 2, 3, 4] ; 
List = [[1, 2], [3, 4], 1, 2] ; 
List = [[1, 2], [3, 4], 3, 4] ; 
List = [[1, 2, 3], [4], 1, 2, 3] ; 
List = [[1, 2, 3], [4], 4] ; 
false. 

所以我得到了我想要的東西，但我得到它的兩倍，並有附加了一些其他的事情。 將在3個部分事情變得更糟糕：

?- partition(3, [1,2,3,4], List). 
List = [[1], [2, 3, 4], [2], [3, 4], 2] ; 
List = [[1], [2, 3, 4], [2], [3, 4], 3, 4] ; 
List = [[1], [2, 3, 4], [2, 3], [4], 2, 3] ; 
List = [[1], [2, 3, 4], [2, 3], [4], 4] ; 
List = [[1, 2], [3, 4], [1], [2], 1] ; 
List = [[1, 2], [3, 4], [1], [2], 2] ; 
List = [[1, 2], [3, 4], [3], [4], 3] ; 
List = [[1, 2], [3, 4], [3], [4], 4] ; 
List = [[1, 2, 3], [4], [1], [2, 3], 1] ; 
List = [[1, 2, 3], [4], [1], [2, 3], 2, 3] ; 
List = [[1, 2, 3], [4], [1, 2], [3], 1, 2] ; 
List = [[1, 2, 3], [4], [1, 2], [3], 3] ; 
false. 

另一個想法是使用前綴，但我不知道怎麼會真正發揮作用。爲了使用它，我應該能夠讓Prolog知道它需要的前綴不能太短，也不能太長，所以我不會選擇一個太長的前綴，因此下一個遞歸步驟沒有剩餘。

任何人都可以指向正確的方向嗎？

小小澄清：謂詞應該返回所有以N部分（不包括空列表）分割列表的可能性。

Answer 1

下面是基本的方式，我想用它來實現一個（使用append/2和length/2）：

list_n_parts(List, Parts, Result) :- 
    length(Result, Parts), 
    append(Result, List). 

現在，沒有按」 t完全符合您的期望：它允許[]。要解決這個問題

一個想法是使用maplist調用格式化事先生成的列表：

list_n_parts(List, Parts, Result) :- 
    length(Result, Parts), 

使用copy_term/2，該maplist/2調用如下：使用functor/3（學分

maplist(copy_term([_|_]), Result), 

@false），它看起來像：

maplist(functor('.', 2), Result), 

使用lambda.pl你可以寫：

maplist(\[_|_]^true, Result), 

因爲 '\' 已經執行期限副本（感謝@false）。

唯一剩下的東西是append/2電話：

append(Result, List). 

另一個想法是使用forall/2過濾（也許簡單搞定，但糟糕的是在複雜性）：

list_n_parts(List, Parts, Result) :- 
    length(Result, Parts), 
    append(Result, List), 
    forall(member(X, Result), X \= []). 

等。 。

Answer 2

當描述涉及列表的關係時，DCG通常非常有用。試想一下：

list_n_parts(List, N, Parts) :- 
     length(Parts, N), 
     phrase(parts(Parts), List). 

parts([]) --> []. 
parts([Part|Parts]) --> part(Part), parts(Parts). 

part([P|Ps]) --> [P], list(Ps). 

list([]) --> []. 
list([L|Ls]) --> [L], list(Ls). 

樣品查詢：

?- list_n_parts([1,2,3,4], 2, Ps). 
Ps = [[1], [2, 3, 4]] ; 
Ps = [[1, 2], [3, 4]] ; 
Ps = [[1, 2, 3], [4]] ; 
false.