Search code examples
listprologdcgdivide

Prolog - dividing a list in N parts


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


Solution

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