Prolog列表排列

Prolog list permutation

我有以下代码生成列表的所有可能排列,但我无法弄清楚它为什么起作用。

remove(X,[X|T],T).
remove(X,[F|T],[F|T1]) :- remove(X,T,T1).

perm([X|Y],Z) :- perm(Y,W), remove(X,Z,W).
perm([],[]).

有人可以给我一些解释或给我发一份参考吗?

我刚开始学习 Prolog,所以我不知道正确的术语,但我认为逻辑如下:

remove(X,L,T)的规则很简单,它将T定义为从L中删除X的列表。例如,给定T=[1],哪个L满足X=2?答案是 [1,2] 或 [2,1].

对于perm,我们以perm([1,2,3], P)为例。

  1. 根据定义,如果W是[2,3]的排列,则P是[1,2,3]的排列,其中W是P去掉1。
  2. 假设我们通过回溯法以某种方式知道 W 是 [2,3] 或 [3,2],那么 P 必须是 [1,2,3],[2,1,3],[2 ,3,1],...
  3. 我们如何找出 [2,3] 的排列是 [2,3] 或 [3,2]?当 W2 是 [3] 的排列时会发生这种情况,其中 W2 是 P2 并删除了 2。
  4. 假设我们以某种方式知道 W2 是 [3],那么 P2 必须是 [2,3] 或 [3,2]。
  5. 我们如何找出 [3] 的排列是 [3]?当 W3 是 [] 的排列时会发生这种情况,其中 W3 是 P3 并删除了 3。由于基本情况,W3 必须是 [],因此 P3 必须是 [3].

刚刚了解了跟踪模式,它提供了一步一步的解释:

?- trace.
true.

[trace] 2 ?- perm([1,2],X).
   Call: (7) perm([1, 2], _G22903) ? creep
   Call: (8) perm([2], _G22988) ? creep
   Call: (9) perm([], _G22988) ? creep
   Exit: (9) perm([], []) ? creep
   Call: (9) remove(2, _G22988, []) ? creep
   Exit: (9) remove(2, [2], []) ? creep
   Exit: (8) perm([2], [2]) ? creep
   Call: (8) remove(1, _G22903, [2]) ? creep
   Exit: (8) remove(1, [1, 2], [2]) ? creep
   Exit: (7) perm([1, 2], [1, 2]) ? creep
X = [1, 2] ;
   Redo: (8) remove(1, _G22903, [2]) ? creep
   Call: (9) remove(1, _G22984, []) ? creep
   Exit: (9) remove(1, [1], []) ? creep
   Exit: (8) remove(1, [2, 1], [2]) ? creep
   Exit: (7) perm([1, 2], [2, 1]) ? creep
X = [2, 1] ;
   Redo: (9) remove(1, _G22984, []) ? creep
   Fail: (9) remove(1, _G22984, []) ? creep
   Fail: (8) remove(1, _G22903, [2]) ? creep
   Redo: (9) remove(2, _G22988, []) ? creep
   Fail: (9) remove(2, _G22988, []) ? creep
   Fail: (8) perm([2], _G22988) ? creep
   Fail: (7) perm([1, 2], _G22903) ? creep
false.