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

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

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

В этой теме 4 ответа, 2 участника, последнее обновление  Васильев Владимир Сергеевич 1 месяц, 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;
    • в противном случае (если первый элемент больше не встречается) функция возвращает результат, полученный при рекурсивном вызове, без изменений
  • #3892

    Кстати, если использовать вариант без накапливающего параметра, то не получится избавиться от отсечения. Иногда отсечение не используют, т.к. несмотря на то, что оно позволило повысить эффективность параллельного программирования, программы с отсечением уже нельзя рассматривать как логические высказывания (и использовать для автоматического доказательства теорем, т.к. часть вариантов отбрасывается). Подробнее про это читайте в статье «Введение в логическое программирование«.

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

       
    список_во_множество([], Буфер, Множество):-
      Множество = Буфер.
    список_во_множество([ПервыйЭлемент|ОстальныеЭлементы], Буфер, Множество):-
      входит_в(ПервыйЭлемент, Буфер), 
      список_во_множество(ОстальныеЭлементы, Буфер, Множество).
    список_во_множество([ПервыйЭлемент|ОстальныеЭлементы], Буфер, Множество):-
      NOT(входит_в(ПервыйЭлемент, Буфер)),
      список_во_множество(ОстальныеЭлементы, [ПервыйЭлемент|Буфер], Множество).

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