Find duplicate sublists in a list using Prolog

Question

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 goal is to find sublists repeated more than once. So far I have found a solution to find all the sublists in the 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 each item.

Thanks in advance.

Answer 1

This code is slightly different from your requirements, since all_match / 2 will omit the empty sequence and fail if there are 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). 

Sketch of the idea of ​​the first sentence re / 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]]. 

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

Answer 2

I like the answer of Kay (+1). Here is 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). 

gives

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