Take the 2-minute tour ×

I'm trying to divide a list in Prolog into 3 equal parts (...well, as equal as possible). My algorithm is the following:

  1. Find out the size of the initial list.
  2. Call the procedure with two extra parameters (the size of the list and a counter that will tell me when I should stop adding elements to one list and start adding to another)

The procedure looks like this:

With 4 parameters:


With 2 extra parameters:


Here's my code:

div3([X | Y],A,B,C) :- length([X | Y],Sz),
                       Sz1 is 0,
                       div3([X | Y],A,B,C,Sz,Sz1).

div3([X | Y],A,B,C,Sz,Sz1) :- Sz1 < Sz//3, % am I done adding to the 1st list?
                              append(X,L,A), % add to the 1st list
                              Sz2 is Sz1+1, % increment the counter

div3([X | Y],A,B,C,Sz,Sz1) :- Sz1 < 2*Sz//3, % am I done adding to the 2nd list?
                              append(X,L,B), % add to the 2nd list
                              Sz2 is Sz1+1, % increment the counter

div3([X | Y],A,B,C,Sz,Sz1) :- Sz1 < Sz, % am I done adding to the 3rd list?
                              append(X,L,C),% add to the 3rd list
                              Sz2 is Sz1+1, % increment the counter
share|improve this question
What is the question? –  svick May 22 '11 at 16:13

3 Answers 3

up vote 1 down vote accepted

I think the first part of your code was almost right... What you are looking for is a recursive predicate with 3 base cases and just one recursive clause.

div3([], [], [], []).
div3([X], [X], [], []).
div3([X,Y], [X], [Y], []).
div3([X,Y,Z|Tail], [X|XTail], [Y|YTail], [Z|ZTail]):-
  div3(Tail, XTail, YTail, ZTail).
share|improve this answer
I don't believe it. I was so simple. This works perfectly. Thanks a lot. –  conectionist May 23 '11 at 4:45

there are no end-cases in the code for the recursive predicate div3/5, the first 3 clauses are applied only for div3/3 calls (that's why calls like div3([4,2,42],X,Y,Z) succeed)

also, you call append/3 with an element, not a list, so it fails (unless you have a list of lists but even in that case, it's not what you want)

i would suggest switching to a more "declarative" approach, maybe with a predicate like get_N_elements(List,List_N,Rest) to avoid code repetition too

share|improve this answer

if maintaining source order does not matter, the following should suffice.

divide( []        , []     , []     , []     ) .  % we're done when the source list is exhausted, OR ...
divide( [X]       , [X]    , []     , []     ) .  % - it's only got 1 element, OR ...
divide( [X,Y]     , [X]    , [Y]    , []     ) .  % - it's only got 2 elements
divide( [X,Y,Z|T] , [X|Xs] , [Y|Ys] , [Z|Zs] ) :- % otherwise, split three elements amount the result lists and
  divide(T,Xs,Ys,Zs)                              % - recurse down.
  .                                               %

The code above partitions the list



  • [a,d,g]
  • [b,e]
  • [c,f]

If you wish to maintain the order, this would work, describing what constitutes a correct solution (e.g., lists of lengths as equal as possible) and letting append/3 find the correct solution(s):

divide( L , X , Y , Z ) :-
  append(X,T,L)               , % split X off as a prefix of the source list L
  append(Y,Z,T)               , % divide the remainder (T) into a prefix Y and suffix Z
  length(X,X1)                , % compute the length of X
  length(Y,Y1)                , % compute the length of Y
  length(Z,Z1)                , % compute the length of Z
  min_max([X1,Y1,Z1],Min,Max) , % determine the shortest and longest such length
  Max - Min =< 1 ,              % and ensure that the delta is 1 or less

min_max([],0,0) .
min_max([H|T],Min,Max) :-

min_max([],Min,Max,Min,Max) .
min_max([H|T], T1 , T2 , Min , Max ) :-
  ( H < T1 -> T3 = H ; T3 = T1 ) ,
  ( H > T2 -> T4 = H ; T4 = T2 ) ,

The above basically says

Divide list L into 3 sublists X, Y and Z such that the delta between the lengths of each sublist does not exceed 1.

In this case, you should see the list


divided into

  • [a,b]
  • [c,d]
  • [e,f,g]

One should note that this is non-deterministic and backtracking will find all possible such solutions.

share|improve this answer

Your Answer


