Добавление списка в список списков рекурсивно

Question

Проблема, которую я пытаюсь решить, заключается в следующем:

Мне дан отсортированный список, в котором я должен соединить первый и последний элементы в списке.Затем я должен соединить 2-й и (последний-1) элементы в списке, пока список не станет пустым или не останется 1 элемент.Затем я должен вернуть список пар.

Шаги, которые я решил предпринять для этой проблемы, состояли в том, чтобы сначала проверить, была ли длина списка больше 1. Если это не так, то это означает, что у нас естьсписок из 0 или 1 элементов.

Затем я получаю первый и последний элементы в данном списке, удаляю их из списка, объединяю их в пары, а затем рекурсивно вызываю тот же предикат в новом списке.После того, как я прошел все этапы до 0/1, я снова всплываю и добавляю их в свой список возврата.

Проблема, с которой я столкнулся, заключается в том, что, когда я пытаюсь добавить пару L = [first,last] в мой список возврата, это ошибки.Мой код указан ниже.

T - мой список ввода.

first/2 просто получает первый элемент в списке.pair/3 удаляет некоторую информацию из P1 и P2, а затем создает L = [P1,P2].

getMatches(T,K,ReturnList) :-
   (  length(T,Val),
      Val > 1, 
      first(T,P1), 
      last(T, P2),
      delete(T,P1,G),
      delete(G,P2,H),
      pair(P1,P2,L),
      getMatches(H,K,ReturnList),
      append(L,K,ReturnList)
   ;  first(T,_),
      K = []
   ).

Пример использования: если T = [1, 2, 3, 4, 5], то ReturnList = [[1,5], [2, 4]] должно удерживаться.

Answer 1

Мы определяем list_pairs/2 на основе общедоступного предиката списка append/3.

list_pairs([] , []).
list_pairs([_], []).
list_pairs([A,B|Xs0], [A-Z|Yss]) :-
   <a href="https://www.complang.tuwien.ac.at/ulrich/iso-prolog/prologue#append" rel="nofollow">append</a>(Xs, [Z], [B|Xs0]),
   list_pairs(Xs, Yss).

Обратите внимание, что мы не представляем пару X и Y каксписок [X,Y], а скорее как составной X-Y.Это соглашение идиоматично, широко распространено и более эффективно!

Вот наиболее общий запрос из list_pairs/2:

?- list_pairs(Es, Pss).
   Es = []                 , Pss = []
;  Es = [_]                , Pss = []
;  Es = [A,B]              , Pss = [A-B]
;  Es = [A,_,B]            , Pss = [A-B]
;  Es = [A,B,C,D]          , Pss = [A-D,B-C]
;  Es = [A,B,_,C,D]        , Pss = [A-D,B-C]
;  Es = [A,B,C,D,E,F]      , Pss = [A-F,B-E,C-D]
;  Es = [A,B,C,_,D,E,F]    , Pss = [A-F,B-E,C-D]
;  Es = [A,B,C,D,E,F,G,H]  , Pss = [A-H,B-G,C-F,D-E]
;  Es = [A,B,C,D,_,E,F,G,H], Pss = [A-H,B-G,C-F,D-E]
...

Answer 2

Это продолжение этого более раннего ответа и его улучшение избегая создания бесполезных точек выбора и снижение сложности Big-O с O (N ² ) до O (N).

list_pairs_lin([], []).
list_pairs_lin([X|Xs], XYs) :-
   <a href="http://www.swi-prolog.org/pldoc/doc_for?object=reverse/2" rel="nofollow noreferrer">reverse</a>(Xs, Ys),
   ahead_keys_values_pairs(Xs, [X|Xs], Ys, XYs).

ahead_keys_values_pairs([], _, _, []).
ahead_keys_values_pairs([_|Fs0], [X|Xs], [Y|Ys], [X-Y|XYs]) :-
   maybe_ahead(Fs0, Fs),
   ahead_keys_values_pairs(Fs, Xs, Ys, XYs).

maybe_ahead([], []).
maybe_ahead([_|Xs], Xs).

Давайте запустим несколько запросов с SWI-Prolog 7.3.15!

Получаем ли мы звуковые ответы при использовании list_pairs_lin/2?

?- <a href="https://www.complang.tuwien.ac.at/ulrich/iso-prolog/prologue#length" rel="nofollow noreferrer">length</a>(Es, N), <a href="http://www.swi-prolog.org/pldoc/doc_for?object=numlist/3" rel="nofollow noreferrer">numlist</a>(1, N, Es), list_pairs_lin(Es, Pss).
   N = 1, Es = [1]                , Pss = []
;  N = 2, Es = [1,2]              , Pss = [1-2]
;  N = 3, Es = [1,2,3]            , Pss = [1-3]
;  N = 4, Es = [1,2,3,4]          , Pss = [1-4,2-3]
;  N = 5, Es = [1,2,3,4,5]        , Pss = [1-5,2-4]
;  N = 6, Es = [1,2,3,4,5,6]      , Pss = [1-6,2-5,3-4]
;  N = 7, Es = [1,2,3,4,5,6,7]    , Pss = [1-7,2-6,3-5]
;  N = 8, Es = [1,2,3,4,5,6,7,8]  , Pss = [1-8,2-7,3-6,4-5]
;  N = 9, Es = [1,2,3,4,5,6,7,8,9], Pss = [1-9,2-8,3-7,4-6]
...

Да! А как насчет сложности?

?- <a href="http://www.swi-prolog.org/pldoc/doc_for?object=set_prolog_flag/2" rel="nofollow noreferrer">set_prolog_flag</a>(<a href="http://www.swi-prolog.org/pldoc/man?section=flags" rel="nofollow noreferrer">toplevel_print_anon</a>, false).
true.

?- <a href="http://www.swi-prolog.org/pldoc/doc_for?object=numlist/3" rel="nofollow noreferrer">numlist</a>(1, 5000, _Xs), <a href="http://www.swi-prolog.org/pldoc/doc_for?object=time/1" rel="nofollow noreferrer">time</a>(<a href="https://stackoverflow.com/a/29866271/4609915">list_pairs</a>(_Xs,_)).
% <b>6,252,500 inferences</b>, 2.302 CPU in 2.301 seconds (100% CPU, 2716404 Lips)
<i>true ;              % succeeds, but leaves behind useless choicepoint</i>
% 2,503 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 1716259 Lips)
false.              % terminates universally

?- numlist(1, 5000, _Xs), time(list_pairs_lin(_Xs,_)).
% <b>10,003 inferences</b>, 0.003 CPU in 0.003 seconds (100% CPU, 3680523 Lips)
true.                % <i>succeeds deterministically</i>

Answer 3

getMatches(List, ReturnList) :-        % getMatches/2
    getMatches(List, [], Answer),
    reverse(Answer, ReturnList),
    !.

getMatches(List, ListAns, ListAns) :-  % getMatches/3
    length(List, L),
    L < 2.
getMatches([H | Tail], List, Ans) :-
    last(Tail, Last),
    delete(Tail, Last, NewTail),
    append([[H, Last]], List, NewList),
    getMatches(NewTail, NewList, Ans).

И

?- getMatches([1,2,3,4,5],X).
X = [[1, 5], [2, 4]].