Генерация всех возможных сочетаний

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

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

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

    questioner
    Участник

    Я прочитал про генерацию Генарация сочетаний заданной длины, однако мне необходимо сгенерировать сочетания всех возможных длин. Это нужно для решения задач на перебор вариантов, например, Задача о ранце на Prolog. Перебор должен проходить в следующем порядке:
    Генерация сочетаний всех возможных длин

  • #2248

    Можно вызвать правило compromise для каждого значения от нуля до length(SourceList), однако, это будет не очень эффективно.
    По изображенному на рисунке дереву можно понять, что функция должна использовать дополнительный буфер для хранения уже сгенерированной части размещения. Например, при генерации цепочки (1->2->3), последовательность (1->2) уже должна быть в буфере.

    Если исходный список пуст — функция должна возвращать значение, накопленное в буфере.
    В противном случае, список разделяется на голову и хвост. Голова списка может быть либо добавлена к буферу, либо нет — для обоих вариантов необходимо выполнить генерацию рекурсивно.

    all_length_compromise([], Compromise, Compromise).
    all_length_compromise([Head|Tail], Buffer, Compromise):-
      compromise_variant(Buffer, Head, BufferVariant),
      all_length_compromise(Tail, BufferVariant, Compromise).
    
    compromise_variant(TailCompromise, Head, [Head|TailCompromise]).
    compromise_variant(TailCompromise, _Head, TailCompromise).

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