title: Prolog: how to write (and use) a function that lists all list permutations?
body: <p>I've found such an example of naive sort written in prolog and I am trying to understand it:</p>
  
  <pre><code>naive_sort(List,Sorted):-perm(List,Sorted),is_sorted(Sorted).
  
  is_sorted([]).
  is_sorted([_]).
  is_sorted([X,Y|T]):-X=&lt;Y,is_sorted([Y|T]).
  
  
  perm(List,[H|Perm]):-delete(H,List,Rest),perm(Rest,Perm).
  perm([],[]).
  
  delete(X,[X|T],T).
  delete(X,[H|T],[H|NT]):-delete(X,T,NT).
  </code></pre>
  
  <p>Naive_sort call works correctly but I just can't figure out why. The main problem is the permutation. When it is called implicitly it always returns only one value. How is it then possible that in naive_sort function call all permutations are checked? Also how could I modify perm function to write all permutations?</p>