/* 

  Global constraint symmetric_all_different and symmetric_all_different_no_fixpoint in Picat.

  From Global Constraint Catalogue
  http://www.emn.fr/x-info/sdemasse/gccat/Csymmetric_alldifferent.html
  """
  All variables associated with the succ attribute of the NODES collection should be 
  pairwise distinct. In addition enforce the following condition: if variable 
  NODES[i].succ takes value j then variable NODES[j].succ takes value i. 
  This can be interpreted as a graph-covering problem where one has to cover a 
  digraph G with circuits of length two in such a way that each vertex of G belongs 
  to one single circuit.
  
  Example
  (
  <
  index-1 succ-3,
  index-2 succ-4,
  index-3 succ-1,
  index-4 succ-2
  >
  )
  
  The symmetric_alldifferent constraint holds since:
    * NODES[1].succ=3 <-> NODES[3].succ=1,
    * NODES[2].succ=4 <-> NODES[4].succ=2.
  """

  * Symmetric alldifferent (allowing fixpoints)

    N = 3:
    [1,2,3]
    [1,3,2]
    [2,1,3]
    [3,2,1]


    N = 4
    [1,2,3,4]
    [1,2,4,3]
    [1,3,2,4]
    [1,4,3,2]
    [2,1,3,4]
    [2,1,4,3]
    [3,2,1,4]
    [3,4,1,2]
    [4,2,3,1]
    [4,3,2,1]

  Number of solutions (go3/0):
    1 = 1
    2 = 2
    3 = 4
    4 = 10
    5 = 26
    6 = 76
    7 = 232
    8 = 764
    9 = 2620
   10 = 9496
   11 = 35696
   12 = 140152
   13 = 568504
   14 = 2390480
   15 = 10349536

  1,2,4,10,26,76,232,764,2620,9496,35696,140152,568504,2390480,10349536
  OEIS: https://oeis.org/A000085
  "Number of self-inverse permutations on n letters, also known as involutions; 
   number of standard Young tableaux with n cells."


  * Symmetric all different not allowing fix points

    N = 3: no solution

    N = 4:
    [2,1,4,3]
    [3,4,1,2]
    [4,3,2,1]

   Number of solitions (go4/0)
     1 = 0
     2 = 1
     3 = 0
     4 = 3
     5 = 0
     6 = 15
     7 = 0
     8 = 105
     9 = 0
    10 = 945
    11 = 0
    12 = 10395
    13 = 0
    14 = 135135
    15 = 0

  0,1,0,3,0,15,0,105,0,945,0,10395,0,135135,0
  OEIS: https://oeis.org/A123023
  "a(n) = (n-1)*a(n-2), a(0)=1, a(1)=0.
   ...
   a(n) is the number of fixed-point free involutions in the symmetric group of degree 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.

go =>
  N = 4,
  X = new_list(N),
  X :: 1..N,

  symmetric_all_different(X),

  solve(X),
  
  println(X),
  fail,
  nl.


go2 =>
  N = 4,
  X = new_list(N),
  X :: 1..N,

  symmetric_all_different_no_fixpoints(X),

  solve(X),
  
  println(X),
  fail,
  nl.


% Number of solutions for symmetric_all_different/1
go3 =>
  member(N,1..15),
  X = new_list(N),
  X :: 1..N,
  Counts = count_all((symmetric_all_different(X),solve($[ff,split],X))),
  println(N=Counts),
  fail,
  nl.


% Number of solutions for symmetric_all_different_no_fixpoints/1
go4 =>
  member(N,1..20),
  X = new_list(N),
  X :: 1..N,
  Counts = count_all((symmetric_all_different_no_fixpoints(X),solve($[ff,split],X))),
  println(N=Counts),
  fail,
  nl.

%
% Note: This version do not assume that a is of even length, which
% means that fixpoints is allowed. E.g. the following are the four
% solutions for n = 3 (where there are at least one fixpoint):
%
% x: [1, 2, 3]
% x: [1, 3, 2]
% x: [2, 1, 3]
% x: [3, 2, 1]
%
symmetric_all_different(X) =>
   all_different(X),
   foreach(I in 1..X.len)
      % X[X[I]] #= I
      element(X[I],X,I)
   end.

symmetric_all_different_no_fixpoints(X) =>
   symmetric_all_different(X),
   foreach(I in 1..X.len)
     X[I] #!= I % no fixpoint
   end.