序言 - 在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.