Вычисление списка всех возможных комбинаций, содержащих произвольные n элементов из заданного списка элементов

Question

Я сталкиваюсь с проблемой в том, как написать программу на Прологе, которая берет список элементов и размер и возвращает список всех возможных комбинаций элементов с заданным размером.

Вот конкретный пример для выяснения проблемы:

?- comb([a, b, c, d, e], 3, L).
L = [a,b,c] ;
L = [a,b,d] ;
L = [a,b,e] ;
... 

Поскольку я новичок в Прологе, я хотел бы получить некоторые подсказки для решения этой проблемы.

Я собираюсь исправить один элемент, а затем применить рекурсию к остальным позициям. Но мне не хватает представления о том, как это реализовать.

Заранее спасибо за советы:)!

Answer 1

Самый простой подход - использование типичного рекурсивного шаблона в Прологе.

Существует тривиальный базовый случай, в котором длина равна 0:

comb(_, 0, []).

Этот случай говорит, что если у меня длина 0, то подсписок является пустым списком. Это верно независимо от полного списка, поэтому мы используем _, так как нам все равно, что это такое.

Рекурсивно, у вас есть два возможных способа, чтобы третий аргумент мог быть подсписком длины N первого аргумента:

1. Если у меня есть список [X|Xs] (первый элемент - X, а остальная часть списка - Xs) и длина N, то одно условие состоит в том, что N > 0, поскольку регистр 0 уже позаботился о. Кроме того, подсписок S будет выглядеть как [X|T], где T - это подсписок Xs и имеет длину N1, где N1 на единицу меньше N.

2. Если у меня есть список [X|Xs] (первый элемент - X, а остальная часть списка - Xs) и длина N, тогда у меня будет условие N > 0 в этом случае также подсписок S будет подсписком Xs длиной N. Так как в этом случае меня не волнует X, я могу написать его как _.

Это описывает, на словах, что должен делать ваш предикат, и предлагает два предложения предиката. Здесь я придерживался другого подхода, нежели тот, который я впервые рассматривал, когда предложил в своем комментарии к вашему вопросу использовать предикат length/2. Выше не нужно использовать этот предикат.

Дополнительный кредит

Если вы используете CLP (FD), который является способом рассуждения Пролога с целыми числами, вы можете легко получить более общее решение, используя вышеуказанный подход. В CLP (FD) вы бы использовали N #> 0 вместо N > 0 и N1 #= N - 1 вместо N1 is N - 1. Используя этот подход, вы можете получить следующие результаты:

| ?- length(List, 3), comb(List, N, Sublist).

List = [_,_,_]
N = 0
Sublist = [] ? a

List = [A,_,_]
N = 1
Sublist = [A]

List = [A,B,_]
N = 2
Sublist = [A,B]

List = [A,B,C]
N = 3
Sublist = [A,B,C]

List = [A,_,B]
N = 2
Sublist = [A,B]

List = [_,A,_]
N = 1
Sublist = [A]

List = [_,A,B]
N = 2
Sublist = [A,B]

List = [_,_,A]
N = 1
Sublist = [A]

no
| ?-

или это ...

| ?- length(List, 5), comb(List, N, [a,b]).

List = [a,b,_,_,_]
N = 2 ? ;

List = [a,_,b,_,_]
N = 2 ? ;

List = [a,_,_,b,_]
N = 2 ? ;

List = [a,_,_,_,b]
N = 2 ? ;

List = [_,a,b,_,_]
N = 2 ? ;

List = [_,a,_,b,_]
N = 2 ? ;

List = [_,a,_,_,b]
N = 2 ? ;

List = [_,_,a,b,_]
N = 2 ? ;

List = [_,_,a,_,b]
N = 2 ? a

List = [_,_,_,a,b]
N = 2

no
| ?-