How does this permutation algorithm work?

Question

ar([],[]). ar([p(_,_)|L],L1):-ar(L,L2),L1=L2. ar([p(X,Y)|L],L1):-ar(L,L2),L1=[p(X,Y)|L2]. 

(p denotes a point having coordinates X and Y)

Please help me understand how the result is constructed, especially the part where L1 gets a new value, thanks!

Answer 1

Defining your predicate ar/2 behaves like a powerset function, being a syntactic version of the following (where X limited to p/2 terms):

 % clause 1: base case ps([], []). % clause 2: omit the element X ps([_X|Y], Z) :- ps(Y, Z). % clause 3: keep the element X ps([X|Y], [X|Z]) :- ps(Y, Z). 

The ps/2 predicates (and your ar/2 ) are basically returned to bind all the list subscriptions in the first argument to the second argument. He achieves this with the choice presented by the second and third caveats: either omit or save the list item when building a new list.

Consider what Prolog does when fulfilling its goal ps([a,b],L) :

• ps([_|[b]], Z) :- ps([b], Z). (via point 2, fall a ).
  • ps([b|[]], Z) :- ps([], Z). (through point 2, drop b , note that [b] = [b|[]] ).
    • ps([], Z) binds Z = [] (through point 1, it gives solution 1).
  • ps([b|[]], [b|Z]) :- ps([], Z). (via point 3, hold b ).
    • ps([], Z) binds Z = [] (through paragraph 1, it gives solution 2).
• ps([_|[b]], [a|Z]) :- ps([b], Z). (through point 3, hold a ).
  • ps([b|[]], Z) :- ps([], Z). (via point 2, drop b ).
    • ps([], Z) binds Z = [] (through point 1, it gives solution 3).
  • ps([b|[]], [b|Z]) :- ps([], Z). (via point 3, hold b ).
    • ps([], Z) connects Z = [] (through point 1, it gives solution 4).

Each of the deepest levels that fall into the “base register” in section 1 returns a call stack. Each of these cases leads to the following:

• Put both a and b : []
• Drop a , hold b : [b]
• Save a , drop b : [a]
• Save both a and b : [a,b]

Thus, we can return to the generation of [] , [b] , [a] and [a,b] , i.e. four subscriptions for [a,b] .

Answer 2

First of all, note that this procedure does not calculate the permutation, but is a kind of sublist: a list with deleted "some" points, where "some" is indicated in general form (one solution is an empty list, and another solution is source list), assuming the input list is well-formed.

If the input list is not formed correctly (it has one element that is not a “point”), then the procedure will fail.

Now let's explain three ar/2 sentences, which are a recursive procedure:

First sentence

 ar([], []). 

indicates that if the first argument is an empty list, then the second argument is also an input list; that is, for an empty list, the only “sublist” that complies with the rules of procedure is also an empty list. This is also the base case of a recursive procedure.

Second sentence

 ar([p(_,_)|L], L1):-ar(L, L2), L1=L2. 

can be rewritten without using the variable L2 , because it ultimately combines with L1 :

 ar([p(_,_)|L], L1):-ar(L, L1). 

This section skips the header of the input list and continues with recursion. When the recursion returns, it will combine the resulting list (second argument to ar/2 ) with the second argument to the sentence chapter.

Third sentence

 ar([p(X,Y)|L], L1):-ar(L, L2), L1=[p(X,Y)|L2]. 

can be rewritten again without using the L2 variable by constructing the resulting list in the sentence header:

 ar([p(X,Y)|L], [p(X,Y)|L1]):-ar(L,L1). 

In this section, we will examine the list of input data, continue the recursion with the tail, and then combine the second argument of the sentence chapter with the received element and the resulting recursion list. That is, it will save the element (head) of the input list along with the result of the recursion.

Also note that this procedure is not reversible if called with the first argument that is not initialized, and the second argument created will be executed forever.