prolog - 为什么找到这么多正确的解决方案？

Question

假设我有一个“基本原子”列表和一个仅由这些基本原子组成的较长原子。允许重复。我编写了以下代码来生成可能构成较长原子的所有原子的列表。这段代码似乎可以正常工作，但它会发现许多重复的相同(正确)解决方案，我不确定为什么？

basics([a, abc, def, aaa]).
  
candidate(aaaabcaaadef).

join_atoms(Atoms, Atom):- join_atoms( Atoms, '', Atom ) .
 
join_atoms( [],    Atom,      Atom ) . 
join_atoms( [H|T], AtomAccum, Atom ) :- 
    atom_concat( AtomAccum, H, UpdatedAtom) ,
    join_atoms( T, UpdatedAtom, Atom ) . 

split_atoms( C, Atoms ):- split_atoms( C, [], Atoms ) .

split_atoms( '', AtomsAccum, Atoms ) :-
    candidate(C) ,
    reverse( AtomsAccum, AtomsAccumR ) ,
    join_atoms( AtomsAccumR, C ) ,
    Atoms = AtomsAccumR .
split_atoms(C, AtomsAccum, Atoms):- 
    basics( B ) ,
    member( SubAtom, B ) ,
    sub_atom( C, _, Length, _, SubAtom ) , 
    sub_atom( C, Length, _, 0, AtomRest ) , 
    split_atoms(AtomRest, [SubAtom|AtomsAccum], Atoms).  

main:-
    candidate( C ) ,
    findall( Atoms, split_atoms(C, Atoms), AllAtoms ) ,
    sort( AllAtoms, UniqueAtoms ) , 
    write(UniqueAtoms),
    nl .

当然，findall/3 和 sort/2 将获取所有解决方案并删除重复项。但如果没有这些，正确的解决方案会重复多次。

例如(输出被截断)

| ?- split_atoms(aaaabcaaadef, Atoms).

Atoms = [a,a,a,abc,a,a,a,def] ? a

Atoms = [a,a,a,abc,a,a,a,def]

Atoms = [a,a,a,abc,a,a,a,def]

Atoms = [a,a,a,abc,a,a,a,def]

Atoms = [a,a,a,abc,a,a,a,def]

Atoms = [a,a,a,abc,a,a,a,def]

Atoms = [a,a,a,abc,aaa,def]

Atoms = [a,a,a,abc,a,a,a,def]

Atoms = [a,a,a,abc,a,a,a,def]

.
.
.

谁能解释为什么会这样？大概出于某种原因，它的回溯超出了必要？或者也许我的代码无意中造成了一种可以最小化的情况？

Answer 1

我觉得你想多了。

解释你的问题陈述:

I want find all the different, distinct ways a given symbol can be composed from an alphabet of shorter symbols.

解决这个问题需要一些观察:

• 较长的符号必须以字母表中较短的符号之一作为前缀
• 如果您从较长的符号中去除这样的前缀，则以上递归成立

这导致了这个简单的解决方案:https://swish.swi-prolog.org/p/tLTQiVNQ.pl

[ sub_atom/5是一个 ISO 标准的内置谓词，可让您按偏移量和长度分解原子]

% --------------------------------------
% compose( Atom, Subatoms, Composition )
% --------------------------------------
compose( ''   , _        , []     ) .  % the empty set composes the empty atom
compose( Atom , Subatoms , [A|As] ) :- % otherwise...
  member(A,Subatoms) ,                 % - fish a symbol out of our alphabet
  sub_atom(Atom,0,L,P,A) ,             % - see if its a prefix of our candidate
  sub_atom(Atom,L,P,_,Nextatom) ,      % - get the next atom (the suffix)
  compose(Nextatom, Subatoms,As)       % - and recurse down
  .                                    % Easy!

鉴于您的示例数据:

?- compose( aaaabcaaadef, [a,abc,def,aaa], Xs).

回溯产生以下结果:

Xs = [a, a, a, abc, a, a, a, def]
Xs = [a, a, a, abc, aaa, def]
Xs = [aaa, abc, a, a, a, def]
Xs = [aaa, abc, aaa, def]
false