Prolog subgroup of list of size n

2
votes

I'm trying to create a rule to determine if a list is a sublist of size n of another list.

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

For example, isSubgroup([1, 2, 4], [1, 2, 3, 4, 5], 3) would return True

However, isSubgroup([4, 2, 1], [1, 2, 3, 4, 5], 3) would return False (because of the different order)

I thought of checking for each member of the subgroup whether or not it's a member of the large group, but that would ignore the order.

Is the idea feasible?

3
prolog
Hint: try to come up with an inductive definition. – Willem Van Onsem
Another hint: Do it on paper first and then write down the instructions as if you were giving it to someone else to do. Then translate that into Prolog. Odds are you can write down the steps, but then will have trouble translating that to Prolog. That is probably the question you then want to post as an update to this question. – Guy Coder
@CapelliC: That likely is Turing, and Turing is not the only one. In fact Dijkstra almost never worked on a machine himself, all was written on paper. – Willem Van Onsem
Related question: Prolog: Compare 2 Lists and find out if at least one member of the first list exists in the other one – Guy Coder
To give an additional hint: you can scan both lists at the same time to check if the current element is the same in both lists. If so, consider the next element of both lists; if not, consider the same element of the subgroup list and the next element of the group list. – damianodamiano

3 Answers

2
votes

Really, try to write an inductive relation. Meanwhile, library(yall) coupled with library(apply) can make one liner:

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

As @WillemVanOnsem suggested, an inductive solution:

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).
0
votes

We can define this predictate by an inductive definition. A Subgroup is a subgroup of Group if:

  1. the Subgroup is an empty list;
  2. the first element of the Subgroup is the same as the first element of Group, and the rest of the Subgroup is a subgroup of the rest of the Group;
  3. the Subgroup is a subgroup of the rest of the Group.

We need to update N accordingly such that, if the Subgroup is empty, then the length is 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).

The above however results in duplicate trues for the same subgroup. This is due to the fact that we can satisfy the predicate in multiple ways. For example if we call:

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

then it is satisfied through the fact (1), but the last clause (3) also calls this with isSubgroup([], [1], 0)., that will then get satisfied through the fact (1), etc.

We can avoid this by making the last clause more restrictive:

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).

The above works for the given "directions" (all arguments should be grounded, are "input"). But typically one wants to use a predicate in other directions as well. We can implement a version that works basically when we use arguments as "output" as well, and still make use of tail-call optimization (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).

For example:

?- 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 .

Here Prolog is thus able to propose groups for which [1,4,2] is a subgroup, and it is capable to determining the length N of the subgroup.

We can query in the opposite direction as well:

?- 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.

Prolog can, for a given group [1,4,2] enumerate exhaustively all possible subgroups, together with N the length of that subgroup.