Пролог - разделение списка на 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. 

Другая идея состоит в использовании префикса, но я не знаю, как это будет действительно работать. Чтобы использовать это, я должен позволить Прологу узнать, что ему нужно взять префикс, который не слишком короткий и не слишком длинный, поэтому я не беру префикс, который слишком длинный, поэтому на следующий шаг рекурсии не осталось ничего.

Может ли кто-нибудь указать мне правильное направление?

Небольшое пояснение: предикат должен возвращать все возможности разделения списка в 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 вызов выглядит следующим образом:

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 \= []). 

и т.д ..

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.