检查列表之间的数字是否相等？

Question

什么是检查序言中列表之间有多少个相等结尾数字的有效方法？

例如我们有 Lista = [4432,2345,3243] 和 Listb = [3345,3232].

在这两个列表中，我们有 4432 和 3232，它们有 2 个相同的结尾数字 和 3345 , 2345 有 3 个相同的结尾数字 . 3243 、 3232 具有相同的 2 个起始数字，但我不认为这是有效的。我已经以最慢的方式解决了这个问题，通过检查 Lista 的每个数字和 Listb 的每个数字，但这是非常慢。我怎样才能更有效地解决这个问题？

编辑 1：我对答案代码进行了一些更改我设法找到了相同的数字和剩余的子树，但是我无法将它们组合起来以准确找到数字一个列表的元素与它们具有相同的数字。你能帮我继续吗？

same_ending(Tree, N /*4904*/, N-Len-Last) :-
  atom_chars(N, Digs),
  reverse(Digs, RDigs),
  same_ending1(RDigs, Tree, [], Fin, 0, Lens),
  pow2(Lens, Res1),
  Res is Res1-1,
  Len = Res,
  Last = Fin.

same_ending1([], _, Curr, Fin, Len, Len).
same_ending1([Dig|Digs], Tree, Curr, Fin, Len, Len2) :-
  ( select(Dig-SubTree, Tree, _) ->
    ( succ(Len, Len1), append([Dig], Curr, Currn),
      same_ending1(Digs, SubTree, Currn, Fin, Len1, Len2) ) 
    ; 
    Len2 = Len,
    Fin = Curr-Tree
  ).

编辑 2：对于@gusbro 的回答的最后建议，我创建了这段代码

ssame_endings(L1,[],Curr,Final):- Final=Curr.

ssame_endings(L1, L2,Curr,Final):-
  build_tree(L1, Tree),
  head(L2,H),
  tail(L2,T),  
  findall(Res,same_ending(Tree,H,Res) , Endings),
  append(Curr,Endings,Curr1),
  ssame_endings(L1,T,Curr1,Final).

head([A|_],A).
tail([_|A],A).

pow2(X,Z) :- Z is 2**X.

same_ending(Tree,N, N-Len/LItems):-
  atom_chars(N, Digs),
  reverse(Digs, RDigs),
  same_ending1(RDigs, Tree, 0, Len, SubTree),
  length(SDigs, Len),
  append(SDigs, _, RDigs),
  reverse(SDigs, RSDigs),
  same_ending2(SubTree, RSDigs, [], LItems).

same_ending1([], SubTree, Len, Len, SubTree1):-
  SubTree=[] -> SubTree1=[[]]; SubTree1=SubTree.
same_ending1([Dig|Digs], Tree, Len, Len2, SubTree):-
  (select(Dig-DigSubTree, Tree,Third) ->
    (succ(Len, Len1), same_ending1(Digs, DigSubTree, Len1, Len2, SubTree),same_ending1(Digs,Third,Len1,Len2,SubTree)) ;
    Len2-SubTree=Len-Tree
  ).

我按照建议使用了 findall 以合并所有给出的答案，我认为这部分是正确的，因为我写了它。然后我在那之后使用了 select 据我所知，如果我们有树 [1-[2-[3,4]] 并且我们想要 1,2,3和 1,2,4。如果我们有数字 5321，第三个参数也会给我们 124。但是我使用它的方式并没有产生预期的结果。我做错了什么？

Answer 1

您可以为第一个列表构建一棵反转数字的树，然后为第二个列表中的每个反转项目遍历树。如果列表有很多项目，这可能会更有效。

same_endings(L1, L2, Endings):-
  build_tree(L1, Tree),
  maplist(same_ending(Tree), L2, Endings).

same_ending(Tree, N, N-Len):-
  atom_chars(N, Digs),
  reverse(Digs, RDigs),
  same_ending1(RDigs, Tree, 0, Len).

same_ending1([], _, Len, Len).
same_ending1([Dig|Digs], Tree, Len, Len2):-
  (select(Dig-SubTree, Tree, _) ->
    (
        succ(Len, Len1), 
        same_ending1(Digs, SubTree, Len1, Len2)
    ) ;
    Len2=Len
  ).

build_tree(L, Tree):-
  foldl(add_tree, L, [], Tree).

add_tree(N, Tree, NTree):-
  atom_chars(N, Digs),
  reverse(Digs, RDigs),
  add_tree1(RDigs, Tree, NTree).

add_tree1([], Tree, Tree).
add_tree1([Dig|Digs], Tree, [Dig-SubTree1|Tree1]):-
  (select(Dig-SubTree, Tree, Tree1) -> true; SubTree-Tree1=[]-Tree),
  add_tree1(Digs, SubTree, SubTree1).

测试样本：

?- same_endings( [4432,2345,3243] , [3345,3232], Endings).
Endings = [3345-3, 3232-2].

您可以稍微修改此代码以获得具有相同结尾的实际项目。

稍微修改上面的代码，您还可以列出第一个列表中具有相同（最大）结尾的第二个列表中每个项目的实际数字：

same_endings(L1, L2, Endings):-
  build_tree(L1, Tree),
  maplist(same_ending(Tree), L2, Endings).

same_ending(Tree, N, N-Len/LItems):-
  atom_chars(N, Digs),
  reverse(Digs, RDigs),
  same_ending1(RDigs, Tree, 0, Len, SubTree),
  length(SDigs, Len),
  append(SDigs, _, RDigs),
  reverse(SDigs, RSDigs),
  same_ending2(SubTree, RSDigs, [], LItems).

same_ending1([], SubTree, Len, Len, SubTree).
same_ending1([Dig|Digs], Tree, Len, Len2, SubTree):-
  (memberchk(Dig-DigSubTree, Tree) ->
    (
        succ(Len, Len1), 
        same_ending1(Digs, DigSubTree, Len1, Len2, SubTree)
    ) ;
    Len2-SubTree=Len-Tree
  ).

same_ending2([], _, LItems, LItems).
same_ending2([Dig-DigSubTree|SubTree], Digs, MItems, LItems):-
  (Dig=endmarker -> 
    (
        number_chars(Item, Digs), 
        NItems=[Item|MItems]
    ) ;
    same_ending2(DigSubTree, [Dig|Digs], MItems, NItems)
  ), 
  same_ending2(SubTree, Digs, NItems, LItems).

build_tree(L, Tree):-
  foldl(add_tree, L, [], Tree).

add_tree(N, Tree, NTree):-
  number_chars(N, Digs),
  reverse(Digs, RDigs),
  add_tree1(RDigs, Tree, NTree).

add_tree1([], Tree, [endmarker-[]|Tree]).
add_tree1([Dig|Digs], Tree, [Dig-SubTree1|Tree1]):-
  (select(Dig-SubTree, Tree, Tree1) -> true; SubTree-Tree1=[]-Tree),
  add_tree1(Digs, SubTree, SubTree1).

测试用例：

?- same_endings( [4432,2345,3243] , [3345,3232], Endings).
Endings = [3345-3/[2345], 3232-2/[4432]].
?- same_endings( [4432,2345,3243,2195345,2345] , [3345,3232,19232,2195345], Endings).
Endings = [3345-3/[2195345, 2345, 2345], 3232-2/[4432], 19232-2/[4432], 2195345-7/[2195345]].

对于项目不共享任何结束数字的情况，没有特殊处理，在这种情况下，代码只是吐出整个列表。

如果您想获得至少有 1 个匹配结束数字的所有项目，只需将过程 same_endings 和 same_endings1 更改为这些：

same_endings(L1, L2, Endings):-
  build_tree(L1, Tree),
  findall(Ending, (member(N, L2), same_ending(Tree, N, Ending)), Endings).

same_ending1([], SubTree, Len, Len, SubTree).
same_ending1([Dig|Digs], Tree, Len, Len2, SubTree):-
  (select(Dig-DigSubTree, Tree, RestTree) ->
    ( 
     (
       Len\=0, 
       RestTree \= [], 
       Len2=Len, 
       SubTree=RestTree
     ) ;
     (
       succ(Len, Len1), 
       same_ending1(Digs, DigSubTree, Len1, Len2, SubTree)
     )
    ) ;
    Len2-SubTree=Len-Tree
  ).

Answer 2

shared_tail_len_atom(A,B,N,S) :-
    sub_atom(A,_,N,0,S),
    N>=1, % raise this value to reduce overhead
    sub_atom(B,_,N,0,S).

same_endings_easy(As,Bs,Es) :-
    setof(N-ab(A,B),
          aggregate(
              max(C),
              S^( member(A,As),
                  member(B,Bs),
                  shared_tail_len_atom(A,B,C,S)
              ), N), Es).

您可以试试这个简单的片段。 sub_atom/5 它是一个内置的 ISO Prolog，但它与数字一起工作的事实可能是一个 SWI-Prolog 扩展。

?- same_endings_easy([123,223,333],[423,433],Endings).
Endings = [1-ab(123, 433), 1-ab(223, 433), 1-ab(333, 423), 2-ab(123, 423), 2-ab(223, 423), 2-ab(333, 433)].

检查列表之间的数字是否相等？

Checking equal digits of numbers between lists?

prolog

clpfd