Пролог - разделение списка на N частей - PullRequest
Новая
       10

Пролог - разделение списка на N частей

1 голос
/ 03 января 2012

Я пытаюсь написать предикат, который делит список на 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 частей (не включая пустые списки).

Ответы [ 2 ]

5 голосов
/ 03 января 2012

При описании отношений, которые включают списки, 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.
3 голосов
/ 03 января 2012

Вот базовый способ, который я бы использовал для реализации этого (используя 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 \= []).

и т.д ...

...