/* 

  Global constraint allperm in Picat.

  From Global Constraint Catalogue
  """
  Given a matrix of domain variables, enforces that the first row is 
  lexicographically less than or equal to all permutations of all other rows.
  
  Example
  (
   <
    vec-<1, 2, 3>,
    vec-<3, 1, 2>
   >
  )

  The allperm constraint holds since vector <1, 2, 3> is lexicographically 
  less than or equal to all the permutations of vector <3, 1, 2> 
  (i.e., <1, 2, 3>, <1, 3, 2>, <2, 1, 3>, <2, 3, 1>, <3, 1, 2>, <3, 2, 1>).
  """


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

*/

import cp.

main => go.


go ?=>
  N = 3, % number of columns
  M = 4, % number of rows
  X = new_array(M,N),
  X :: 1..10,

  X = {
      {2,3,9},
      {_,_,_},
      {_,_,_},
      {_,_,_}
      },

  all_different(X[1]),
  allperm(X,Ps), 

  Vars = X ++ Ps,
  solve(Vars),

  foreach(Row in X) println(Row) end,
  % println(ps=Ps),
  nl,

  fail,
  
  nl.

go => true.


%
% allperm
% 
allperm(X,Ps) =>
   N = X.len,
   M = X[1].len,
   Ps0 = [],
   foreach(I in 2..N)
       P = new_list(M),
       P :: 1..M,
       all_different(P),
       permutation3(X[1],P,X[I]),
       lex_le(X[1],X[I]),
       Ps0 := Ps0 ++ {P}
   end,
   Ps = Ps0.
       

%
% The permutation from A <-> B using the permutation P
%
permutation3(A,P,B) =>
   foreach(I in 1..A.length)
       %  B[I] #= A[P[I]]
       PI #= P[I], 
       BI #= B[I], 
       element(PI, A, BI)
   end.


% Port of MiniZinc's lex2.mzn 
% """
%-----------------------------------------------------------------------------%
% Require adjacent rows and adjacent columns in the array 'x' to be
% lexicographically ordered.  Adjacent rows and adjacent columns may be equal.
%-----------------------------------------------------------------------------%
% """
% Note: This use lex_less/1.
lex2(X) =>
   Len = X[1].length,
   foreach(I in 2..X.length) 
      lex_lt([X[I-1,J] : J in 1..Len], [X[I,J] : J in 1..Len])
   end.

% This use lex_lesseq/1
lex2eq(X) =>
   Len = X[1].length,
   foreach(I in 2..X.length) 
      lex_le([X[I-1,J] : J in 1..Len], [X[I,J] : J in 1..Len])
   end.