Генерация размещений и перестановок на Prolog

      Комментарии к записи Генерация размещений и перестановок на Prolog отключены

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

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

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

    questioner
    Участник

    Помогите написать программу на SWI Prolog для генерации размещений без повторений и перестановок (комбинаторных объектов).
    Размещения в отличии от сочетаний являются упорядоченным набором элементов, т.е. наборы, состоящие из одних и тех же элементов, но стоящих в разном порядке являются различными.
    В SWI Prolog встроена функция permutation, позволяющая генерировать перестановки, но ее нельзя использовать. Перестановки списка из nэлементов можно получить как размещения длины n.

  • #2072

    Для генерации размещений длины k нужно на каждую позицию от 1 до k поставить каждый из возможных элементов исходного множества. Требуются размещения без повторения — значит нужно либо проверять каждый из полученных вариантов на наличие повторов, либо удалять уже поставленный элемент из исходного списка (а после рекурсивной обработки — возвращать элемент назад).

    Чтобы выбирать элементы списка можно использовать встроенную функцию member, а для удаления — функцию delete. Если в вашем диалекте нет таких функций — реализации можно скопировать из статьи по обработке списков на Prolog.

    permutation(_List, 0, []):-!.
    permutation(List, PermutationLength, [Head|PermutationTail]):-
      member(Head, List),
      delete(List, Head, ListTail),
      PermutationTailLength is PermutationLength - 1,
      permutation(ListTail, PermutationTailLength, PermutationTail).

    Если требуется выдать размещения нулевой длины — функция возвращает пустой список.
    В остальных случаях произвольно выбирается элемент списка при помощи функции member. Полученное значение удаляется из списка функцией delete. Длина списка уменьшается и выполняется рекурсивная обработка, в результате которой вычисляется частичный результат, к которому добавляется значение, полученное предикатом member.
    Предикат member гарантированно переберет все элементы исходного списка в процессе поиска решения, значит на первую позицию размещений гарантированно будут поставлен каждый элемент исходного списка. На вторую позицию будут подбираться все элементы, кроме того, который поставлен первым (ведь тот элемент окажется уже удаленным). И так далее для каждой из k позиций.

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

    permutation(List, Permutation):-
      length(List, Length), 
      permutation(List, Length, Permutation).

  • #2882

    Вместо предикатов member и delete можно использовать один вызов стандартного предиката select:

    permutation(_List, 0, []).
    permutation(List, PermutationLength, [Head|PermutationTail]):-
      select(Head, List, ListTail), 
      PermutationTailLength is PermutationLength - 1,
      permutation(ListTail, PermutationTailLength, PermutationTail).

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