Пролог подгруппы списка размера n

Действительно, попробуйте написать индуктивное отношение. Между тем библиотека (yall) в сочетании с библиотекой (apply) может сделать один вкладыш:

isSubgroup(S,G,N) :- length(S,N),
    foldl({G}/[E,P,X]>>(nth1(X,G,E),X>=P),S,1,_F).

Как предложил @WillemVanOnsem, индуктивное решение:

subGroups([], []).

subGroups([X|Xs], [X|Ys]):-
    subGroups(Xs, Ys).

subGroups(Xs, [_|Ys]):-
    subGroups(Xs, Ys).

subGroupsN(Options, N, Solution) :-
    length(Solution, N),
    subGroups(Solution, Options).

Мы можем определить этот предикат с помощью индуктивного определения. Subgroup является подгруппой Group, если:

1. Subgroup является пустым списком;
2. первый элемент Subgroup совпадает с первый элемент Group, а остальная часть Subgroup является подгруппой остальной части Group;
3. Subgroup является подгруппой остальной части Group. [ 1127]

Нам нужно обновить N соответственно так, чтобы, если Subgroup пусто, то длина была 0:

isSubgroup([], _, 0).              %% (1)
isSubgroup([H|TS], [H|TG], N) :-   %% (2)
    N1 is N-1,
    isSubgroup(TS, TG, N1).
isSubgroup(S, [_|TG], N) :-        %% (3)
    isSubgroup(S, TG, N).

Однако приведенное выше приводит к дублирующим истинам для та же самая подгруппа. Это связано с тем, что мы можем удовлетворить предикат несколькими способами. Например, если мы вызываем:

isSubgroup([], [1,2], 0).

, то это удовлетворяется посредством факта (1), но последний пункт (3) также вызывает это с помощью isSubgroup([], [1], 0)., который затем будет удовлетворен посредством факта ( 1) и т. Д.

Мы можем избежать этого, сделав последнее предложение более ограничительным:

isSubgroup([], _, 0).              %% (1)
isSubgroup([H|TS], [H|TG], N) :-   %% (2)
    N1 is N-1,
    isSubgroup(TS, TG, N1).
isSubgroup([HS|TS], [_|TG], N) :-  %% (3)
    isSubgroup([HS|TS], TG, N).

Вышеуказанное работает для данных «направлений» (все аргументы должны быть обоснованы, являются «входными»). Но обычно каждый хочет использовать предикат и в других направлениях. Мы можем реализовать версию, которая работает в основном, когда мы используем аргументы в качестве «вывода», и при этом по-прежнему используем оптимизацию хвостовых вызовов (TCO) :

isSubgroup(S, G, N) :-
    isSubgroup(S, G, 0, N).

isSubgroup([], _, L, L).              %% (1)
isSubgroup([H|TS], [H|TG], L, N) :-   %% (2)
    L1 is L+1,
    isSubgroup(TS, TG, L1, N).
isSubgroup([HS|TS], [_|TG], L, N) :-  %% (3)
    isSubgroup([HS|TS], TG, L, N).

Например:

?- isSubgroup([1,4,2], G, N).
G = [1, 4, 2|_2974],
N = 3 ;
G = [1, 4, _2972, 2|_2986],
N = 3 ;
G = [1, 4, _2972, _2984, 2|_2998],
N = 3 ;
G = [1, 4, _2972, _2984, _2996, 2|_3010],
N = 3 .

Здесь Пролог, таким образом, может предлагать группы, для которых [1,4,2] является подгруппой, и он способен определять длину N подгруппы.

Мы также можем запросить в противоположном направлении:

?- isSubgroup(S, [1,4,2], N).
S = [],
N = 0 ;
S = [1],
N = 1 ;
S = [1, 4],
N = 2 ;
S = [1, 4, 2],
N = 3 ;
S = [1, 2],
N = 2 ;
S = [4],
N = 1 ;
S = [4, 2],
N = 2 ;
S = [2],
N = 1 ;
false.

Пролог может для данной группы [1,4,2] исчерпывающе перечислить все возможные подгруппы, вместе с N длину этой подгруппы. [ 1138]