Ответ в теме: Выделить из списка неубывающие подпоследовательности

      Комментарии к записи Ответ в теме: Выделить из списка неубывающие подпоследовательности отключены
#2155

Для решения задачи нужно выделять по очереди элементы из списка и выполнять их вставку в список последовательностей. При добавлении очередного элемента нужно иметь информацию о предыдущем обработанном значении и если они образуют неубывающую последовательность, то необходимо выполнить вставку нового значения в конец подпоследовательности. А если не образуют – создать новую подпоследовательность.
Вставка элемента в конец списка выполняется эффективно не во всех реализациях языка Prolog – если внутри языка используются односвязные списки то асимптотическая оценка сложности такой вставки – O(N), а сложность всего алгоритма – O(N^2). Вставка элемента в начало списка гарантированно выполняется быстро. Поэтому может быть рационально перевернуть исходный список перед обработкой – по крайней мере, такой прием стоит использовать если нам нужна эффективная хвостовая рекурсия.
Однако, если элементов не очень много, то можно использовать не хвостовую рекурсию:

non_decreasing_sequences([], []):-!.
non_decreasing_sequences([Head|Tail], Sequences):-
  non_decreasing_sequences(Tail, TailSequences),
  insert_to_non_decreasing(Head, TailSequences, Sequences).

Если исходный список пуст – то результатом должен быть пустой список подпоследовательностей. Если же в нем есть хотя бы один элемент – нужно выполнить разделение на голову и хвост, выполнить рекурсивную обработку хвоста, а к полученном результату добавить голову. Вставка головы выделена в отдельную функцию, которая должна посмотреть на следующий элемент и в зависимости от отношения порядка выполнить либо добавление новой подпоследовательности, либо вставку в начало существующей:

insert_to_non_decreasing(Element, [], [[Element]]):-!.
insert_to_non_decreasing(Element, [[Head|Tail]|TailList], [[Element, Head|Tail]|TailList]):-
  Head >= Element, !.
insert_to_non_decreasing(Element, TailList, [[Element]|TailList]).

Если до сих пор не было создано ни одной подпоследовательности – то она создается из вставляемого элемента. В противном случае список последовательностей разделяется на голову (первая последовательность) и хвост (TailList). Первая последовательность также разделяется на Head и Tail. Затем происходит вставка в зависимости от результата сравнения Head и Element.