这个Prolog代码到底是如何工作的-洗牌两个列表

例如,当您试图在Prolog中证明一个目标时: shuffle([a],[c],L). Prolog所做的是在数据库中进行搜索,以找到与谓词shuffle相关的规则。

在这种情况下,第二条规则和第三条规则同时出现,因此您有两个选项选择点,如Prolog中所述:

:我们检查第二条规则: shuffle([X|Xs],Ys,[X|Zs]):- shuffle(Xs,Ys,Zs). [X|Xs] = [a] X = a, Xs = [] Ys = [c] ,和 L 是那种形式的 [a|Zs] shuffle([],[c],Zs) Zs = [c|Zs'] 又一次递归地 shuffle([],[],Zs') 现在只有第一个规则匹配,我们得到 Zs' = [] Zs = [a,c] . 现在我们留下了另一个案例:

第二选择点 :我们检查第三条规则: shuffle(Xs,[Y|Ys],[Y|Zs]):- shuffle(Xs,Ys,Zs). 把它应用到我们的目标中 Xs = [a], [Y|Ys] = [c] Y = c, Ys = [] 我 是那种形式的 [c|Zs] shuffle([a],[],Zs) 被称为。这个进球现在只符合第二条规则,我们得到了 Zs = [a|Zs'] 随机播放([],[],Zs') 现在只有第一个规则匹配,我们得到 . 所以从第二个病例来看 Zs = [c,a] .

shuffle([a,b],[c,d],L) ?? 这将是四个选择点,对于 Xs,Ys

避开所有的X,Y和Z部分,我们能说什么 工作 代码:

1. 您可以从以下查询开始 shuffle([1,2],[a,b],L). Prolog试图通过解决三个问题来解决这个问题 shuffle 规则。
2. 洗牌 规则。
3. 不管找到什么解决办法 必须 shuffle -> shuffle -> [shuffle....] -> empty lists

Prolog将尝试从规则的顶部解决:

From the top:

A) shuffle([1,2],[a,b],L).  -no->  shuffle([],[],[]).
B) shuffle([1,2],[a,b],L).  -??->  shuffle([X|Xs],Ys,[X|Zs]):- shuffle(Xs,Ys,Zs).
B) shuffle([1,2],[a,b],L).  -??->  shuffle([X=1|Xs=[2]],Ys=[a,b],[X=1|Zs=??]) :- shuffle(Xs=[2],Ys=[a,b],Zs).

% A) fails as [1,2] does not match with []
% B) partially binds but is missing Zs. Solving to try and find the Zs is now:

shuffle(Xs=[2],Ys=[a,b],Zs).



From the top:

A) shuffle([2],[a,b],Zs).  -no->  shuffle([],[],[]).
B) shuffle([2],[a,b],Zs).  -??->  shuffle([X|Xs],Ys,[X|Zs]):- shuffle(Xs,Ys,Zs).
B) shuffle([2],[a,b],Zs).  -??->  shuffle([X=2|Xs=[]],Ys=[a,b],[X=2|Zs=??]):- shuffle(Xs,Ys,Zs).

% A) fails as [2] does not match with []
% B) partially binds but is missing Zs. Solving to try and find the Zs is now:

shuffle(Xs=[],Ys=[a,b],Zs).



From the top:

A) shuffle([],[a,b],Zs).  -no->  shuffle([],[],[]).
B) shuffle([],[a,b],Zs).  -no->  shuffle([X|Xs],Ys,[X|Zs]):- shuffle(Xs,Ys,Zs).
C) shuffle([],[a,b],Zs).  -??->  shuffle(Xs,[Y|Ys],[Y|Zs]):- shuffle(Xs,Ys,Zs).
C) shuffle([],[a,b],Zs).  -??->  shuffle(Xs=[],[Y=a|Ys=[b]],[Y=a|Zs=??]):- shuffle(Xs,Ys,Zs).

% A) fails as [a,b] does not match with the second []
% B) fails as [] does not match with [X|Xs]
% C) partially binds but is missing Zs. Solving to try and find the Zs is now:

shuffle([],[b],Zs).



From the top:

A) shuffle([],[b],Zs).  -no->  shuffle([],[],[]).
B) shuffle([],[b],Zs).  -no->  shuffle([X|Xs],Ys,[X|Zs]):- shuffle(Xs,Ys,Zs).
C) shuffle([],[b],Zs).  -??->  shuffle(Xs,[Y|Ys],[Y|Zs]):- shuffle(Xs,Ys,Zs).
C) shuffle([],[b],Zs).  -??->  shuffle(Xs=[],[Y=b|Ys=[]],[Y=b|Zs=??]):- shuffle(Xs,Ys,Zs).

% A) fails as [b] does not match with the second []
% B) fails as [] does not match with [X|Xs]
% C) partially binds but is missing Zs. Solving to try and find the Zs is now:

shuffle([],[],Zs).



From the top:

A) shuffle([],[],Zs).  -no->  shuffle([],[],[]).

% A) succeeds. Zs can be []

这是一个从原点到空列表的完整链,经过四次洗牌。在此链中,Zs被构造为 [1|?] 然后 [1|[2|?]] [1|[2|[a|?]]] 然后 [1|[2|[a|[b|?]]]] 然后 [1|[2|[a|[b|[]]]]] 完整无缺。与你的 L 输入第一个结果。

它经历了洗牌 B B C C .

但是搜索空间还没有用尽,可能会有更多的答案。如果你问他们,它解开了备份链到一个地方,它可以采取不同的路径。而不是解决 shuffle([X|Xs].. 它可以跳过那一个俯冲下去 shuffle(Xs 相反。

两个 洗牌

[1,2],[a,b],Unknown
        \
         \
          \ ? shuffle shuffle shuffle
          /
         /
         \
      [],[],[]

B B C C A . 另一个链条是 B C B C A L=[1,a,2,b] .

[1,2],[a,b],Unknown
       /   \       
      /     \
      \      \ B C B A
B B C C\     /
       |    /
       |    \
      [],[],[]

一旦它一路返回,在每一个选择中,将洗牌换成另一个,然后沿着链子到空列表,它将找到6条路径,6种方法在洗牌中反弹。

列表越长,链就越长。当它开始回溯链,撤消它的步骤,寻找其他的方式去,有更多的。更多的选择点,所以它会找到更多的解决方案-成比例的长度输入。