4

我想用以下输出编写一个 prolog 谓词：

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

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

提前致谢。

4

2 回答 2

2

此代码与您的要求略有不同，因为 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).

重复/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).
于 2013-06-29T10:58:57.567 回答
2

我喜欢凯的回答（+1）。这里有一个关于 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).

产量

?- setof(L,all_match([1,2,3,2,3,1,2],L),R).
R = [[1], [1, 2], [2], [2, 3], [3]].
于 2013-06-29T11:09:31.157 回答