Prolog - dividing a list in N parts

Question

I'm trying to write a predicate that divides a list into N parts. This is what I have so far.

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

The idea is to keep chopping parts of the list into two other parts until I have N pieces. I have mediocre results with this approach:

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

So I get what I want, but I get it two times and there are some other things attached. When dividing into 3 parts things get worse:

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

Another idea is using prefix but I don't know how that would really work. To use that I should be able to let Prolog know that it needs to take a prefix that's not too short and not too long either, so I don't take a prefix that's too long so there's nothing left for a next recursion step.

Can anyone point me in the right direction?

Little clarification: the predicate should return all posibilities of dividing the list in N parts (not including empty lists).

Answer 1

Here is the basic way I'd use to implement that (using append/2 and length/2) :

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

Now, that doesn't totally complies to your expectations : it allows for [].

One idea to fix that is to use a maplist call to format the Resulting list beforehand :

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

using copy_term/2, the maplist/2 call looks like :

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

using functor/3 (credits to @false), it would look like :

    maplist(functor('.', 2), Result),

using lambda.pl you could write :

    maplist(\[_|_]^true, Result),

since the '\' already performs a term copy (thanks @false).

The only thing left is the append/2 call:

    append(Result, List).

Another idea would be to use forall/2 filtering (maybe simpler to get, but worse in complexity) :

list_n_parts(List, Parts, Result) :-
    length(Result, Parts),
    append(Result, List),
    forall(member(X, Result), X \= []).

etc...

Answer 2

When describing relations that involve lists, DCGs are often very useful. Consider:

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).

Sample query:

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