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)为例。
- 根据定义,如果W是[2,3]的排列,则P是[1,2,3]的排列,其中W是P去掉1。
- 假设我们通过回溯法以某种方式知道 W 是 [2,3] 或 [3,2],那么 P 必须是 [1,2,3],[2,1,3],[2 ,3,1],...
- 我们如何找出 [2,3] 的排列是 [2,3] 或 [3,2]?当 W2 是 [3] 的排列时会发生这种情况,其中 W2 是 P2 并删除了 2。
- 假设我们以某种方式知道 W2 是 [3],那么 P2 必须是 [2,3] 或 [3,2]。
- 我们如何找出 [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.
我有以下代码生成列表的所有可能排列,但我无法弄清楚它为什么起作用。
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)为例。
- 根据定义,如果W是[2,3]的排列,则P是[1,2,3]的排列,其中W是P去掉1。
- 假设我们通过回溯法以某种方式知道 W 是 [2,3] 或 [3,2],那么 P 必须是 [1,2,3],[2,1,3],[2 ,3,1],...
- 我们如何找出 [2,3] 的排列是 [2,3] 或 [3,2]?当 W2 是 [3] 的排列时会发生这种情况,其中 W2 是 P2 并删除了 2。
- 假设我们以某种方式知道 W2 是 [3],那么 P2 必须是 [2,3] 或 [3,2]。
- 我们如何找出 [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.