Преобразовать список в множество – удалить повторы элементов

      Комментарии к записи Преобразовать список в множество – удалить повторы элементов отключены

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

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

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

    questioner
    Участник

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

  • #1952

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

    Нужно использовать метод накапливающего параметра чтобы на i-том шаге был построен результат для предыдущих i-1 шагов, однако в этом случае результат окажется перевернутым. Функции используют стандартные предикаты member и reverse для поиска элемента в списка и реверса списка.

    list_to_set(List, Set):-
      list_to_set(List, [], ReverseSet),
      reverse(ReverseSet, Set).

    Правило вызывает вспомогательную функцию, использующую накаливающий параметр, передавая в качестве начального значения буфера пустой список, а затем, выполняет реверс результата.

    list_to_set([], Buffer, Buffer):-!.
    list_to_set([Head|Tail], Buffer, Set):-
      member(Head, Buffer), !, list_to_set(Tail, Buffer, Set);
      list_to_set(Tail, [Head|Buffer], Set).

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

  • #3201

    Другая реализация предиката менее эффективна, т.к. использует не хвостовую рекурсию, но зато немного проще:

    list_to_set([], []):-!.
    list_to_set([Head|Tail], [Head|TailSet]):-
       NOT(member(Head, Tail)), !,
       list_to_set(Tail, TailSet).
    list_to_set([_Head|Tail], TailSet):-
       list_to_set(Tail, TailSet).

    Если входной список пуст – то результат – пустой список.
    В противном случае список разделяется на первый элемент (Head) и остальные (Tail), а затем:

    • если первый элемент не встречается среди остальных – то Tail обрабатывается рекурсивно и к результату добавляется Head;
    • в противном случае (если первый элемент больше не встречается) функция возвращает результат, полученный при рекурсивном вызове, без изменений

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