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