Проверить, является ли L списком всех последовательностей (списков) длины K из чисел 1, 2, ..., N (swi-prolog)

@Paul4554 · Регистрация: 18.09.2017

Студворк — интернет-сервис помощи студентам

Напишите предикат 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 есть список списков, состоящих из К-1 элементов. Предикат g каждый список А в Y преобразует в список списков вида
[[1|A],[2|A],[3|A],...,[N|A]] (обратите внимание, все внутренние списки имеют длину К) и потом объединяет все эти списки списков, чтобы получить Х.

@Black Fregat · 07.11.2018, 16:12

Сообщение от Paul4554

Если K=0, то результат пустой список.

Это неправильно. Чтобы заработала рекурсия, для К = 0 должно возвращаться [[]]
Это соответствует и логике задачи.

@Paul4554 · 09.11.2018, 09:58 **[ТС]**

Возможно, но так было написано в условии задачи

@Black Fregat · 09.11.2018, 12:44

Prolog
1
2
3
4
5
6
7
8
9
10
11
12
p(_, 0, [[]]) :- !.
p(N, K, L) :-
    KK is K-1,
    p(N, KK, LL),
    g(LL, 1, N, L).
g([], _, _, []).
g([_|T], K, N, LL) :-
    K > N, !,
    g(T, 1, N, LL).
g([H|T], K, N, [[K|H]|TT]) :-
    KK is K+1,
    g([H|T], KK, N, TT).

@Paul4554 · 30.11.2018, 20:53 **[ТС]**

Здорово, спасибо за решение, всё работает, но как новичку, хотелось бы, чтобы добавили комментарии пожалуйста

@Black Fregat · 01.12.2018, 14:57

Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
p(_, 0, [[]]) :- !.   % для цепочек из 0 элементов один вариант - пустая цепочка
p(N, K, L) :-         % иначе для цепочек из К элементов
    KK is K-1,
    p(N, KK, LL),     % рекурсивно генерируется список для цепочек из К-1 элементов
    g(LL, 1, N, L).   % и отдельным предикатом расширяется, как и сказано в задании
 
g([], _, _, []).      % для пустого списка генерируется пустой список
g([_|T], K, N, LL) :- % иначе
    K > N, !,         % если текущее число превысило N, голова отбрасывается
    g(T, 1, N, LL).   % и далее обрабатывается хвост списка, начиная с 1
g([H|T], K, N, [[K|H]|TT]) :- % иначе в результат добавляется сцепление текущего числа с головой списка,
    KK is K+1,        % текущее число увеличивается
    g([H|T], KK, N, TT). % и выполняется рекурсивный вызов с тем же списком, но с новым числом.

Новые блоги и статьи Все статьи Все блоги /
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025	Расскажи мне о Мире, бродяга kumehtar 12.11.2025 — Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .

Проверить, является ли L списком всех последовательностей (списков) длины K из чисел 1, 2, ..., N (swi-prolog)

Решение

Решение

@Paul4554 0 / 0 / 0 Регистрация: 18.09.2017 Сообщений: 5

	Проверить, является ли L списком всех последовательностей (списков) длины K из чисел 1, 2, ..., N (swi-prolog) 07.11.2018, 10:40. Показов 3960. Ответов 5 Метки нет (Все метки) Напишите предикат 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 есть список списков, состоящих из К-1 элементов. Предикат g каждый список А в Y преобразует в список списков вида [[1\|A],[2\|A],[3\|A],...,[N\|A]] (обратите внимание, все внутренние списки имеют длину К) и потом объединяет все эти списки списков, чтобы получить Х. 0

@Paul4554 0 / 0 / 0 Регистрация: 18.09.2017 Сообщений: 5
	09.11.2018, 09:58 [ТС]
	Возможно, но так было написано в условии задачи 0

@Paul4554 0 / 0 / 0 Регистрация: 18.09.2017 Сообщений: 5
	30.11.2018, 20:53 [ТС]
	Здорово, спасибо за решение, всё работает, но как новичку, хотелось бы, чтобы добавили комментарии пожалуйста 0