Ответ в теме: Генерация сочетаний на Prolog

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

Пусть дан список a0, a1, a2 ... an элементов, требуется получить все сочетания (т.е. подмножества) длины k.

  1. первым сочетанием может быть a0, a1, ... ak. В настоящий момент перебраны все сочетания, содержащие элементы с индексами от нуля до k;
  2. последний элемент (ak) удаляется и на его место ставится a{k+1} процесс продолжается пока не будут обработаны все элементы списка. К этому шагу были перебраны все сочетания, содержащие все элементы с индексами от нуля до {k-1};
  3. аналогично обрабатываются последовательности a0, ..., a{k-i} где i изменяется от 1 до {k-1}. В результате будут перебраны все сочетания, содержащие элемент a0;
  4. процесс генерации (шаги 1-3) надо запустить с каждого индекса исходного списка (a1, a2, ... a{n-k}).

Таким образом каждый элемент может быть либо добавлен к результирующему списку, либо пропущен (четвертый пункт алгоритма), при добавлении уменьшается K и процесс может выполняться рекурсивно:

compromise(_List, 0, []):-!.
compromise([Head|Tail], Length, [Head|Sublist]):-
  SublistLength is Length - 1,
  compromise(Tail, SublistLength, Sublist).
compromise([_Head|Tail], Length, Sublist):-
  compromise(Tail, Length, Sublist).