Генерация сочетаний на Prolog

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

Помечено: ,

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

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

    questioner
    Участник

    Помогите написать на языке программирования 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).

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