Prolog - 将列表分为 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.

所以我得到了我想要的东西，但我得到了两次，并且还附加了一些其他东西。 当分成三部分时，情况会变得更糟：

?- 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

当描述涉及列表的关系时，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.

Answer 2

这是我用来实现该功能的基本方法（使用 append/2 和 length/2）：

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

现在，这并不完全符合您的期望：它允许使用[]。

解决这个问题的一个想法是使用 maplist 调用预先格式化结果列表：

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

使用 copy_term/2，maplist/2 调用看起来就像：

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

使用 functor/3 （归功于@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 \= []).

等等。 。