/* 

  Permutation number in Picat.

  A permutation number is the number of transpositions
  in a permutation.
  See http://en.wikipedia.org/wiki/Permutation

  Number of different permutations number for a specific n:
  n = 10:
  perm_num = 10: 21670
  perm_num =  9: 13640
  perm_num =  8: 8095
  perm_num =  7: 4489
  perm_num =  6: 2298
  perm_num =  5: 1068
  perm_num =  4: 440
  perm_num =  3: 155
  perm_num =  2: 44
  perm_num =  1: 9
  perm_num =  0: 1

  n = 6
  perm_num = 6: 90
  perm_num = 5: 71
  perm_num = 4: 49
  perm_num = 3: 29
  perm_num = 2: 14
  perm_num = 1: 5
  perm_num = 0: 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 = 6,
  X = new_list(N),
  X :: 1..N,


  % array[1..n] of var 0..n: transpositions; % number of reversals
  PermNum :: 0..N, % if the permutation is even/odd
  EvenOdd :: 0..1, % if the permutation is even/odd

  all_different(X),
  permutation_number(X, PermNum),

  EvenOdd #= PermNum mod 2,
  % PermNum #= 2,
  % PermNum #= 1,

  Vars = X ++ [PermNum,EvenOdd],
  solve(Vars),

  println(x=X),
  println(permNum=PermNum),
  println(evenOdd=EvenOdd),
  nl,
  fail,

  nl.

go => true.

%
% Collect statistics
%
go2 ?=>
  nolog,
  foreach(N in 2..10)
    println(n=N),
    Map = get_global_map(N),
    permutation_number_stats(N, Map),
    foreach(K in Map.keys.sort_down)
      println(perm_num=K=Map.get(K))
    end,
    nl
  end,
  
  nl.

go2 => true.

%
% Get a statistics map of permutation numbers for
% a certain N.
%
permutation_number_stats(N, Map) ?=>
  X = new_list(N),
  X :: 1..N,

  PermNum :: 0..N, % if the permutation is even/odd
  EvenOdd :: 0..1, % if the permutation is even/odd

  all_different(X),
  permutation_number(X, PermNum),

  EvenOdd #= PermNum mod 2,

  Vars = X++ [PermNum,EvenOdd],
  solve([updown],Vars),
  
  Map.put(PermNum,Map.get(PermNum,0)+1),
  fail.

permutation_number_stats(_N, _Map) => true.
  

permutation_number(X, PermNum) =>
  N = X.len,
  Transpositions2 = new_list(N),
  Transpositions2 :: 0..N,
  foreach(I in 1..N)
     % count the number of elements in I+1 which are lower than
     % X[I]. This is the number of reversals
     Transpositions2[I] #= sum([X[J] #< X[I] : J in I+1..N])
  end,
  PermNum #= sum(Transpositions2).