/* 

  Constrained permutations in Picat.

  From Jean-Louis Laurier 
  "A Language and a Program for Stating and Solving Combinatorial Problems" (page 42ff, 72ff)
  and in 
  Jean-Louis Laurier "Problem Solving and Artififical Intelligence" (pages 440ff)

  The problem is attributed to M. P. Schützenberger.

  P is a permutation (1..N). The problem is to find all permutations that satisfies
  two constraints on these binary arrays (of length N-1)

  * "monotone":
    M[I] = 1 <=> P[I+1] > P[I]

  * "advance":
    A[I] = 0 <=> P[I]+1 is to the left of P[I]
    A[I] = 1 <=> P[I]+1 is to the right of P[I] and P[I] != N


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

*/

import cp.

main => go.

% Example from Laurier "Problem Solving and Artififical Intelligence" (p 440)
go =>
  % The only solution is [3,1,2,4]
  N = 4,
  M = [0,1,1], 
  A = [1,1,0], 

  constrained_perm(N,M,A,P),
  println(m=M),
  println(a=A),
  println(p=P),
  nl,
  fail,
  nl.  

/*
  Example from Laurier "Problem Solving and Artififical Intelligence" (p 443f)

  Here are the 42 solutions satisfying the given M and A (and sorted for convenience):

    p = [1,2,5,3,9,6,7,4,8]
    p = [1,2,6,3,9,4,7,5,8]
    p = [1,2,7,3,6,4,8,5,9]
    p = [1,2,7,5,6,3,8,4,9]
    p = [1,2,8,3,9,4,6,5,7]
    p = [1,2,8,3,9,5,6,4,7]
    p = [1,2,8,4,9,5,6,3,7]
    p = [1,2,8,5,9,3,6,4,7]
    p = [1,3,8,4,9,5,6,2,7]
    p = [1,4,5,2,9,6,7,3,8]
    p = [1,4,7,5,6,2,8,3,9]
    p = [1,4,8,2,9,5,6,3,7]
    p = [1,4,8,5,9,2,6,3,7]
    p = [1,5,6,2,9,3,7,4,8]
    p = [1,5,7,2,6,3,8,4,9]
    p = [1,5,8,2,9,3,6,4,7]
    p = [1,6,7,2,5,3,8,4,9]
    p = [1,6,7,4,5,2,8,3,9]
    p = [1,7,8,2,9,3,5,4,6]
    p = [1,7,8,2,9,4,5,3,6]
    p = [1,7,8,3,9,4,5,2,6]
    p = [1,7,8,4,9,2,5,3,6]
    p = [2,3,8,4,9,5,6,1,7]
    p = [2,7,8,3,9,4,5,1,6]
    p = [3,4,5,1,9,6,7,2,8]
    p = [3,4,7,5,6,1,8,2,9]
    p = [3,4,8,1,9,5,6,2,7]
    p = [3,4,8,5,9,1,6,2,7]
    p = [3,6,7,4,5,1,8,2,9]
    p = [3,7,8,1,9,4,5,2,6]
    p = [3,7,8,4,9,1,5,2,6]
    p = [4,5,6,1,9,2,7,3,8]
    p = [4,5,7,1,6,2,8,3,9]
    p = [4,5,8,1,9,2,6,3,7]
    p = [4,6,7,1,5,2,8,3,9]
    p = [4,7,8,1,9,2,5,3,6]
    p = [5,6,7,1,4,2,8,3,9]
    p = [5,6,7,3,4,1,8,2,9]
    p = [6,7,8,1,9,2,4,3,5]
    p = [6,7,8,1,9,3,4,2,5]
    p = [6,7,8,2,9,3,4,1,5]
    p = [6,7,8,3,9,1,4,2,5]

  Found in 0.05s

*/
go2 =>
  N = 9,

  M = [1,1,0,1,0,1,0,1],  
  A = [1,1,1,1,0,1,1,0],
  
  % P = [6,7,8,1,9,2,4,3,5], % Testing one of the solution from page 444. OK

  constrained_perm(N,M,A,P),
  println(m=M),
  println(a=A),
  println(p=P),
  nl,
  fail,
  nl.  


%
% M = A = [1,0,0,0.....0] (1,then all 0s)
% This is mentioned at page 445
% For N there are N-1 solutions, with P[2] #= N.
% 
% For N = 10, the 9 solutions are
% p = [9,10,8,7,6,5,4,3,2,1]
% p = [8,10,9,7,6,5,4,3,2,1]
% p = [4,10,9,8,7,6,5,3,2,1]
% p = [3,10,9,8,7,6,5,4,2,1]
% p = [5,10,9,8,7,6,4,3,2,1]
% p = [2,10,9,8,7,6,5,4,3,1]
% p = [6,10,9,8,7,5,4,3,2,1]
% p = [1,10,9,8,7,6,5,4,3,2]
% p = [7,10,9,8,6,5,4,3,2,1]
%
go3 =>
  nolog,
  N = 30,
  M = [1] ++ [0 : I in 2..N-1],
  A = [1] ++ [0 : I in 2..N-1],
  
  constrained_perm(N,M,A,P),
  println(m=M),
  println(a=A),
  println(p=P),
  nl,
  fail,
  nl.  

%
% Generate all N! solutions for N in 1..10
%
go4 =>
  member(N,1..10),
  nl,
  println(n=N),
  constrained_perm(N,M,A,P),
  println(m=M),
  println(a=A),
  println(p=P),
  nl,
  fail,
  nl.  
  

constrained_perm(N,M,A,P) =>

  M = new_list(N-1),
  M :: 0..1,

  A = new_list(N-1),
  A :: 0..1,

  P = new_list(N),
  P :: 1..N,
  
  % all_different(P),
  all_distinct(P), % faster than all_different/1
  
  foreach(I in 1..N-1)
    M[I] #= 1 #<=> P[I+1] #> P[I],
    
    A[I] #= 0 #<=>  sum([P[J] #= P[I] + 1 : J in I+1..N]) #= 0,
    A[I] #= 1 #<=> (sum([P[J] #= P[I] + 1 : J in 1..I-1]) #= 0 #/\ P[I] #!= N)
  end,
  solve($[ff,split],P).