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

      Комментарии к записи Ответ в теме: Генерация размещений и перестановок на Prolog отключены
#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).