1

我正在尝试编写一个将列表分成 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 部分的所有可能性（不包括空列表）。

4

2 回答 2

5

在描述涉及列表的关系时，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.
于 2012-01-03T13:46:19.427 回答
3

这是我用来实现它的基本方法（使用append/2and 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 \= []).

ETC...

于 2012-01-03T14:05:33.200 回答