prolog - 使用 Prolog 在列表中查找重复子列表

Question

我想编写一个具有以下输出的序言谓词:

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

目的是找到重复多次的子列表。到目前为止，我找到了查找列表中所有子列表的解决方案-

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

但我不知道如何重复搜索每个元素。

提前致谢。

Answer 1

此代码与您的要求略有不同，因为 all_match/2 将省略空序列，并且如果输入中没有重复的子序列则失败。

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

repeated/2 第一个子句的概念草图:

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

结果:

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

更新以允许重叠序列:

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