/* 

  Global constraint sort_permutation in Picat.

  From Global Constraint Catalogue
  http://www.emn.fr/x-info/sdemasse/gccat/Csort_permutation.html
  """
  sort_permutation(FROM,PERMUTATION,TO)
  
  Purpose

      The variables of collection FROM correspond to the variables of collection TO according 
      to the permutation PERMUTATION. The variables of collection TO are also sorted in 
      increasing order.

  Example
      (
      <1, 9, 1, 5, 2, 1> ,
      <1, 6, 3, 5, 4, 2>,
      <1, 1, 1, 2, 5, 9>
      )

  The sort_permutation constraint holds since:
    * The first item FROM[1].var=1 of collection FROM corresponds to the 
      PERMUTATION[1].var=1th item of collection TO.
    *  The second item FROM[2].var=9 of collection FROM corresponds to the 
       PERMUTATION[2].var=6th item of collection TO.
    * The third item FROM[3].var=1 of collection FROM corresponds to the 
      PERMUTATION[3].var=3th item of collection TO.
    * The fourth item FROM[4].var=5 of collection FROM corresponds to the 
      PERMUTATION[4].var=5th item of collection TO.
    * The fifth item FROM[5].var=2 of collection FROM corresponds to the 
      PERMUTATION[5].var=4th item of collection TO.
    *  The sixth item FROM[6].var=1 of collection FROM corresponds to the 
       PERMUTATION[6].var=2th item of collection TO.
    *  The items of collection TO=1,1,1,2,5,9 are sorted in increasing order.

  Figure 4.270.1. Illustration of the correspondence between the items of the FROM 
  and the TO collections according to the permutation defined by the items of 
  the PERMUTATION collection
  """

  For From = [1,9,1,5,2,1] there are two solutions (due to th repeating 1s):

  from = [1,9,1,5,2,1]
  perm = [1,6,3,5,4,2]
  to   = [1,1,1,2,5,9]

  from = [1,9,1,5,2,1]
  perm = [3,6,1,5,4,2]
  to   = [1,1,1,2,5,9]


  This program was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import cp.

main => go.

go =>
  
  N = 6,
  
  From = new_list(N),
  From :: 1..9,
  
  Permutation = new_list(N),
  Permutation :: 1..N, 

  To = new_list(N),
  To :: 1..9,

  From = [1, 9, 1, 5, 2, 1],
  % Permutation = [1, 6, 3, 5, 4, 2],
  % To = [1, 1, 1, 2, 5, 9],
  
  sort_permutation(From, Permutation, To),

  Vars = From ++ Permutation ++ To,
  solve(Vars),

  println('from'=From),
  println('perm'=Permutation),
  println('to  '=To),
  nl,
  fail,
  nl.


%
% sort_permutation
% Note: If permutation is not fixed and From (and thus To) has more than one
% occurrence of some value then there will be many solutions.
%
sort_permutation(From, Permutation,To) => 
    all_different(Permutation),
    increasing(To), % the sort part
    
    % the permutation part
    foreach(I in 1..From.len)
       element(Permutation[I],To,From[I]),
       element(Permutation[I],From,To[I])
    end.