CODEWITHSUNDEEP
listprologpermutation
Dani Grosu
Dani Grosu

Reputation: 554

Prolog list permutation

I have the following code that generates all possible permutations of a list, but I can't figure it out why it is working.

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([],[]).

Could someone give me some explanation or send me to a reference, please?

Upvotes: 1

Views: 2117

Answers (1)

Fabricator
Fabricator

Reputation: 12782

I'm just picking up Prolog, so I don't know the correct terms, but I think the logic goes as following:

The rules for remove(X,L,T) is straightforward, it defines T as a list with X removed from L. For example, given T=[1], which L satisfies X=2? the answer is [1,2] or [2,1].

For perm, let's take the example of perm([1,2,3], P).

  1. According to the definition, P is a permutation of [1,2,3] if W is a permuation of [2,3], where W is P with 1 removed.
  2. Assuming we somehow know W is [2,3] or [3,2] through the magic of backtracking, then P must be [1,2,3],[2,1,3],[2,3,1],...
  3. How did we find out permutation of [2,3] is [2,3] or [3,2]? It happens when W2 is a permutation of [3], where W2 is P2 with 2 removed.
  4. Assuming we somehow know W2 is [3], then P2 must be [2,3] or [3,2].
  5. How did we find out permutation of [3] is [3]? It happens when W3 is a permutation of [], where W3 is P3 with 3 removed. Since W3 must be [] due to the base case, then P3 must be [3].

Just learned about the trace mode, it provides a step-by-step explanation:

?- 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.

Upvotes: 1

Related Questions