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

Question

Я пытаюсь создать правило, чтобы определить, является ли список подсписком размера n другого списка.

isSubgroup/3
isSubgroup(+Subgroup, +Group, +N)

Например, isSubgroup([1, 2, 4], [1, 2, 3, 4, 5], 3) вернет True

Однако isSubgroup([4, 2, 1], [1, 2, 3, 4, 5], 3) вернет False (из-за другого порядка)

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

Возможна ли идея?

Answer 1

Как предложил @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).

Answer 2

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

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

Нам необходимо соответственно обновить 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 длиной этой подгруппы.

Answer 3

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

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