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

Главная Форумы Программирование Помощь с решением задач на Prolog Задачи на списки Выделить из списка неубывающие подпоследовательности

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 2 года/лет, 6 мес. назад.

  • Автор
    Сообщения
  • #2154

    questioner
    Участник

    Из исходного списка нужно сформировать новый список, в который включить все неубывающие подпоследовательности.
    Например:

    ?- non_decreasing_sequences([3,4,5,4,2,7,5,6,6,8,3], NonDecreasing).
    NonDecreasing = [[3, 4, 5], [4], [2, 7], [5, 6, 6, 8], [3]]

  • #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.

Для ответа в этой теме необходимо авторизоваться.