Пролог - разделить список на 3 части

Question

Я пытаюсь разделить список в Прологе на 3 равные части (... ну, как можно равнее).Мой алгоритм следующий:

1. Узнать размер начального списка.
2. Вызвать процедуру с двумя дополнительными параметрами (размер списка и счетчик, который сообщит мнекогда я должен прекратить добавлять элементы в один список и начать добавлять в другой)

Процедура выглядит следующим образом:

С 4 параметрами:

div3(InitialList,FirstNewList,SecondNewList,ThirdNewList).

С2 дополнительных параметра:

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

Вот мой код:

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

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(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),!.

Answer 1

Я думаю, что первая часть вашего кода была почти правильной ... То, что вы ищете, - это рекурсивный предикат с 3 базовыми случаями и только одним рекурсивным предложением.

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

Answer 2

если поддержание исходного порядка не имеет значения, должно быть достаточно следующего:

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

Код над разделами списка

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

в

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

Если вы хотите сохранить порядок, это сработает, описывая, что представляет собой правильное решение (например, списки длин как можно больше), и позволяя append/3 найти правильное решение (я):

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

Сказанное в основном говорит

Разделите список L на 3 подсписка X, Y и Z так, чтобы дельта между длинами каждый подсписок не превышает 1.

В этом случае вы должны увидеть список

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

делится на

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

Следует отметить, что это недетерминировано, и обратный поиск найдет все возможные такие решения.

Answer 3

в коде для рекурсивного предиката div3 / 5 нет конечных случаев, первые 3 предложения применяются только для вызовов div3 / 3 (именно поэтому такие вызовы, как div3 ([4,2,42], X, Y , Z) успешно)

также вы вызываете append / 3 с элементом, а не со списком, поэтому происходит сбой (если у вас нет списка списков, но даже в этом случае это не то, что вам нужно)

Я бы предложил перейти к более "декларативному" подходу, возможно, с предикатом, таким как get_N_elements (List, List_N, Rest), чтобы также избежать повторения кода