Find repeating sublists in list using Prolog

4
votes

I want to write a prolog predicate with the following output:

?- all_match([1,2,3,2,3,1,2],L).
L = [[], [1], [1, 2], [2], [2, 3], [3]].

?- all_match([1,1,1,2],L).
L = [[], [1], [1, 1]].

The purpose is to find the sublists that repeat more than once. So far I found the solution to find all sublists in a list-

subSet(_, []).
subSet(L, [S|T]) :- append(_, L2,L), append([S|T], _, L2).

But I can't figure out how to repeat the search for every element.

Thanks in advance.

2
prolog

2 Answers

2
votes

I like Kay's answer (+1). Here a variation on thema

all_match(L, M) :-
    take(L, M, R),
    take(R, M, _).

take(L, [A|B], R) :-  % use [A|B] to remove empties
    append(_, T, L),
    append([A|B], R, T).

yields

?- setof(L,all_match([1,2,3,2,3,1,2],L),R).
R = [[1], [1, 2], [2], [2, 3], [3]].
2
votes

This code is a little different from your requirements, in that all_match/2 will omit the empty sequence and fail if there where no repeated subsequences in the input.

repeated(List, Sublist) :-
        % For all prefixes, suffixes:
        append(Sublist, Tail, List), Sublist \= [],
        % For all suffixes of the former suffixes:
        append(_, TailTail, Tail),
        % Is the head of the latter suffix equal to the head of the input?
        append(Sublist, _, TailTail).
repeated([_|List], Sublist) :-
        % Strip leading character and continue
        repeated(List, Sublist).

all_match(List, Lists) :-
        % Aggregate all repeated sequences or fail if there weren't any.
        setof(L, repeated(List, L), Lists).

A sketch of the idea of the first clause of repeated/2:

|----------------List------------------|  repeated(List, Sublist)
|--Sublist--|------------Tail----------|  append(Sublist, Tail, List)
|--Sublist--|       |-----TailTail-----|  append(_, TailTail, Tail)
|--Sublist--|       |--Sublist--|      |  append(Sublist, _, TailTail)

Result:

?- all_match([1,2,3,2,3,1,2],L).
L = [[1], [1, 2], [2], [2, 3], [3]].

Update to allow overlapping sequences:

repeated([H|List], Sublist) :-
        append(Sublist, _, [H|List]), Sublist \= [],
        append(_, Tail, List),
        append(Sublist, _, Tail).
repeated([_|List], Sublist) :-
        repeated(List, Sublist).