Prolog - divide list into 3 parts

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:

div3(InitialList,FirstNewList,SecondNewList,ThirdNewList).

With 2 extra parameters:

div3(InitialList,FirstList,SecondList,ThirdList,InitialListSize,Counter).

Here's my code:

div3([],[],[],[]).
div3([X],[X],[],[]).
div3([X,Y],[X],[Y],[]).
div3([X,Y,Z],[X],[Y],[Z]).
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(Y,L,B,C,Sz,Sz2),!.

d开发者_如何学编程iv3([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(Y,A,L,C,Sz,Sz2),!.

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
                              div3(Y,A,B,L,Sz,Sz2),!.

---

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

---

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

---

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,b,c,d,e,f,g]

into

• [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(T,H,H,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 ) ,
  min_max(T,T3,T4,Min,Max)
  .

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

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

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.