Prolog 中最常见的子列表

Question

问题如下：在Prolog中写一个谓词most_common_sublist(L1,N,L2)，找到长度为N的子列表L2，使得它是L1中最常见的子列表。

//Example 1:
?- most_common_sublist([1,2,2,3,2,2,4,2,2,3],1,L).
L=[2];

//Example 2:
?- most_common_sublist([1,2,2,3,2,2,4,2,2,3],2,L).
L=[2,2];

//Example 3:
?- most_common_sublist([1,2,2,3,2,2,4,2,2,3],3,L).
L=[2,2,3];

我的方法是使用生成器谓词生成所有可能的大小为 N 的子列表，使用检查谓词检查列表中最常见的子列表，然后将其作为我的结果。我不对长度和添加使用内置谓词的原因是因为我应该自己编写。我的生成器谓词有效，它给出了正确的输出。

?- generator([1,2,2,3,2,2,4,2,2,3],3,L).
L = [[1, 2, 2], [2, 2, 3], [2, 3, 2], [3, 2, 2], [2, 2, 4], [2, 4, 2], [4, 2|...], [2|...]] [write]
L = [[1, 2, 2], [2, 2, 3], [2, 3, 2], [3, 2, 2], [2, 2, 4], [2, 4, 2], [4, 2, 2], [2, 2, 3]]

我检查了我所有的谓词，它们似乎都有效（至少对于我正在使用的测试用例而言），问题出现在检查谓词上。在达到 N>=P 之前它似乎工作正常（当这不是真的时，当它是真的时工作正常）。我希望程序继续执行它下面的下一个检查谓词（第三个检查谓词），以便它在 Result 中存储 Temp 值而不是 H 值。由于某种原因，它没有转到第三个检查谓词（我用调试器检查过），而是做了一些奇怪的事情（我不知道是什么）。

most_common_sublist(L,N,Result):-generator(L,N,LOP),check(LOP,_,Temp),add(Temp,[],Result).

add([],L,L).
add([X|L1],L2,[X|L3]):-add(L1,L2,L3).

length([],0).
length([X|O],N):-length(O,M),N is M+1.

sublist([H|_],1,[H]).
sublist([H|T],N,[H|LOP]):-M is N-1,sublist(T,M,LOP).

generator(L,N,[L]):-length(L,M),N=:=M.
generator([H|T],N,LOP):-sublist([H|T],N,PN),generator(T,N,LP),add([PN],LP,LOP).

check([],Z,K):-Z is 0,add([],[],K).
check([H|T],Hits,Result):-check_how_many(H,[H|T],N),check(T,P,_),N>=P,Hits is N,add(H,[],Result).
check([H|T],Hits,Result):-check_how_many(H,[H|T],N),check(T,P,Temp),Hits is P,add(Temp,[],Result).

check_how_many(X,[X],1).
check_how_many(_,[_],0).
check_how_many(Pattern,[H|T],Hits):-same(Pattern,H),check_how_many(Pattern,T,P),Hits is P+1.
check_how_many(Pattern,[_|T],Hits):-check_how_many(Pattern,T,P),Hits is P.

same([], []).
same([H1|R1], [H2|R2]):-
    H1 = H2,
    same(R1, R2).

Answer 1

由于我不熟悉您的代码，所以我用类似的功能重写了它。 %here 后面的行是我的改进（使用了 2 次）。为简单起见，我使用了内置谓词 length/2 和 append/3 而不是 add/3。 sublist/3 具有完全不同的代码但功能相同，根本不需要 same/2。你的大多数用法 add/3 以及一些等式语句都是不必要的。

most_common_sublist(L,N,Temp):-
    generator(L,N,LOP),
    check(LOP,_,Temp).

sublist(L,N,S):-
    length(S,N),
    append(S,_,L).

generator(L,N,[L]):-
    length(L,N).
generator([H|T],N,LOP):-
    sublist([H|T],N,PN),
    generator(T,N,LP),
    append([PN],LP,LOP).

check([],0,[]).
check([H|T],N,H):-
    check_how_many(H,[H|T],N),
    check(T,P,_),
    N>=P.
check([H|T],P,Temp):-
    check_how_many(H,[H|T],N),
    check(T,P,Temp)
%here
    , N=<P
    .

check_how_many(X,[X],1).
check_how_many(_,[_],0).
check_how_many(H,[H|T],Hits):-
    check_how_many(H,T,P),
    Hits is P+1.
check_how_many(Pattern,[H|T],P):-
%here
    Pattern \== H,
    check_how_many(Pattern,T,P).

在放弃跟踪后，我只是在启用长输出后使用以下调用进行调试 (
?- set_prolog_flag(answer_write_options,[max_depth(100)]). ):

?- findall(Temp,check([[1, 2, 2], [2, 2, 1]],_,Temp),Out).

初始输出为

Out = [[1,2,2],[1,2,2],[1,2,2],[1,2,2],[1,2,2],[1,2,2],[1,2,2],[2,2,1],[2,2,1],[],[],[2,2,1],[2,2,1],[],[]].

其中包含很多空列表。第一个修复 (%here) 是为最后一个 check/3 案例设置条件 N=<P。到目前为止，可以选择低于 N 的 P，这应该包含在第二个 check/3 案例中。输出更改为

Out = [[1,2,2],[1,2,2],[1,2,2],[1,2,2],[1,2,2],[2,2,1],[2,2,1],[2,2,1],[]].

更好，但仍然可能出现空列表。最后一个check_how_many/3的情况也有类似的情况：你必须声明H和Pattern是不同的，否则拟合Pattern可能不被计算在内.让我们检查一下输出

Out = [[1,2,2],[1,2,2],[1,2,2],[2,2,1]].

好多了。让我们检查另一个案例：

?- findall(Temp,check([[1, 2, 2], [1, 2, 2], [2, 2, 1]],_,Temp),Out).
Out = [[1,2,2],[1,2,2],[1,2,2],[1,2,2]].

?- findall(Temp,check([[1, 2, 2], [2, 2, 2], [1, 2, 2]],_,Temp),Out).
Out = [[1,2,2],[1,2,2],[1,2,2],[1,2,2],[1,2,2],[1,2,2],[1,2,2],[1,2,2],[2,2,2],[2,2,2],[2,2,2],[1,2,2]].

工作...差不多。

所以问题似乎是check_how_many/3: alter

check_how_many(_,[_],0).

至

check_how_many(_,[],0).

你应该没问题。

?- findall(Temp,check([[1, 2, 2], [2, 2, 2], [1, 2, 2]],_,Temp),Out).
Out = [[1,2,2],[1,2,2],[1,2,2],[1,2,2],[1,2,2],[1,2,2],[1,2,2],[1,2,2]].

由于自己编写代码比调试外部代码更有趣，所以我将尝试添加另一个答案。

Answer 2

自己编写代码比调试外星代码有趣得多。所以这是我的尝试。它的工作方式与您的不同，因为我不计算可能的子集，而是处理“剩余”列表。我使用内置谓词 length/2、append/3 和 member/2，每行写下 3 行。

% check how often 2.nd attribute List occurs in 1st attribute List.
countit([],_,Val,Val). 
countit([H|In],Out,Past,Future):-
    (   append(Out,_,[H|In])
    ->  Present is Past+1,
        countit(In,Out,Present,Future)
    ;   countit(In,Out,Past,Future)
    ).
    
mostCommonSublist(In,N,Out):-
    maxStartList(In,N,OutList,Max),
    member((Max,Out),OutList).

% for every endlist calculate how often the first N elements appear within the endlist, track the max
maxStartList(In,N,[(1,In)],1):-
    length(In,N),
    !.
maxStartList([H|In],N,[(CntH,Curr)|MaxList],Max):-
    length(Curr,N),
    countit([H|In],Curr,0,CntH),
    maxStartList(In,N,MaxList,CntIn),
    Max is max(CntH , CntIn).

主谓词mostCommonSublist/3调用谓词maxStartList/4得到所有sublists/countpairs。之后它验证子列表的计数是否等于最大值。这是检查具有相同（最大）计数的不同答案所必需的。

maxStartList/4 从输入列表中删除元素并计算当前列表的开头在其中出现的频率。它还跟踪最大值。

对于当前输入列表，调用计算谓词countit/4。它为给定的输入列表（第一个参数）计算子列表（第二个参数）的出现次数。
我的代码其实用了一个转折点：第一次调用countit/4时子列表的内容不统一，只是设置了子列表的长度。在第一次递归中，它将所有条目与输入列表中的起始元素统一起来并对其进行计数。在下面的递归步骤中，如果子列表是完全已知的。使用 if-then-else (..->..;..) 剩余输入列表的两种情况是否以子列表开头，谓词基本上计算出现次数。直到剩余的输入列表只剩下N个元素（length(In,N)）。

计算出的 count/sublist 对存储在列表中，最大值也被跟踪。

在知道所有 count/sublist 对后，我通过声明接受的子列表的计数必须等于最大值来最终确定它。

好在没有重复的答案。

?- mostCommonSublist([1,2,2,3,2,2,4,2,2,3],3,L).
L = [2,2,3] ;
false.

?- mostCommonSublist([1,2,2,1,2,1,2,2,2,3],3,L).
L = [1,2,2] ;
L = [2,1,2] ;
false.

?- mostCommonSublist([1,2,2,1,2,1,2,2,2,1],2,L).
L = [1,2] ;
L = [2,2] ;
L = [2,1] ;
false.

Prolog 中最常见的子列表

Most common sublist in Prolog

algorithm

list

prolog

sublist