/*
Global constraint inverse in Picat.
From Global Constraint Catalog
http://www.emn.fr/z-info/sdemasse/gccat/Cinverse.html
"""
inverse(NODES)
Enforce each vertex of a digraph to have exactly one predecessor and
one successor. In addition the following two statements are equivalent:
- The successor of the ith node is the jth node.
- The predecessor of the jth node is the ith node.
"""
Note: This is implemented as "self-assignment", i.e. that
inverse(X) -> assignment(X,X)
This means that for each element X[I] either
- X[I] = I
or
- X[I] = J <=> X[J] = I
Example N=4:
[1,2,3,4]
[1,2,4,3] (X[3]=4, X[4]=3)
[1,3,2,4] (X[2]=3, X[3]=2)
[1,4,3,2]
[2,1,3,4]
[2,1,4,3] (X[1]=2,X[2]=1, X[3]=4,X[4]=3)
[3,2,1,4]
[3,4,1,2]
[4,2,3,1]
[4,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 = 6,
X = new_list(N),
X :: 1..N,
inverse(X),
All = solve_all(X),
foreach(Sol in All)
println(Sol)
end,
println(num=All.length),
nl.
%
% Number of solutions for N=1..11:
% [1,2,4,10,26,76,232,764,2620,9496,35696]
% OEIS:
% http://oeis.org/search?q=1%2C2%2C4%2C10%2C26%2C76%2C232%2C764%2C2620%2C9496%2C35696&language=english&go=Search
%
% http://oeis.org/A000085
% Number of self-inverse permutations on n letters, also known as
% involutions; number of Young tableaux with n cells.
%
go2 =>
Sols = [],
foreach(N in 1..11)
X = new_list(N),
X :: 1..N,
inverse(X),
All = solve_all(X),
println([N,All.length]),
Sols := Sols ++ [All.length]
end,
println(Sols),
nl.
inverse(X) =>
assignment(X,X).