Генерация перестановок длины K из чисел 1,2,…,N

Программирование Помощь с решением задач на Prolog Задачи на списки Генерация перестановок длины K из чисел 1,2,…,N

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

  • Автор
    Сообщения
  • #5336
    @yaroslav

    Здравствуйте, нужна помощь с написанием программы на SWI-Prolog по следующему условию:
    Предикат p(+N, +K, -L) — истинный тогда и только тогда, когда L — список всех последовательностей (списков) длины K из чисел 1,2,...,N
    Пример:

    ?- p(3,2,L).
    L=[[1,1],[2,2],[3,3],[1,2],[1,3],[2,1],[3,1],[2,3],[3,2]];
    No

    (элементы списка могут быть в другом порядке)

    Алгоритм.
    Правила для предиката p(N,K,X):
    Если K=0, то результат пустой список.
    Если K>0, то рекурсивно вызываем p для K-1, получаем результат Y и вызываем вспомогательный предикат g(Y,N,X).
    Что делает предикат g(Y,N,X)?
    Y есть список списков, состоящих из K-1 элементов. Предикат g каждый список A в Y преобразует в список списков вида [[1|A],[2|A],[3|A],…,[N|A]] (все внутренние списки имеют длину K) и потом объединяет все эти списки списков, чтобы получить X.

  • #5339
    @admin

    Алгоритм обязательно такой использовать? — такое ощущение, что его писал человек, не понимающий Prolog.

    Почитать можно тут: «Генерация размещений и перестановок на Prolog».

    Предикат можно написать так:

    p(_Max, 0, []).
    p(Max, Len, [Head|Tail]):-
        Len > 0,
        between(1, Max, Head),
        TailLen is Len - 1,
        p(Max, TailLen, Tail).

  • #5342
    @yaroslav

    @admin думаю, Ваш вариант тоже подойдет. Спасибо большое за ответ!
    Возможно ли вывести результат одним списком, содержащим эти подсписки из перестановок? Не могу додуматься как это сделать

  • #5344
    @yaroslav

    @admin я уже как-то пробовал использовать в своей задаче findall, но преподаватель требует не использовать встроенные предикаты. В этом вся загвоздка.

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