/*

  Derangements in Picat.

  From http://rosettacode.org/wiki/Permutations/Derangements
  """
  Permutations/Derangements
  A derangement is a permutation of the order of distinct items in which 
  no item appears in its original place.

  For example, the only two derangements of the three items 
    (0, 1, 2) are (1, 2, 0), and (2, 0, 1).
  
  The number of derangements of n distinct items is known as the subfactorial of n, 
  sometimes written as !n. There are various ways to calculate !n.

  Task

  The task is to:

   - Create a named function/method/subroutine/... to generate derangements of the integers 
     0..n-1, (or 1..n if you prefer).
   - Generate and show all the derangements of 4 integers using the above routine.
   - Create a function that calculates the subfactorial of n, !n.
   - Print and show a table of the counted number of derangements of n vs. the calculated 
     !n for n from 0..9 inclusive. 

  As an optional stretch goal:

    Calculate !20. 
  """


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

*/

import util.

main => go.

go =>
   foreach(N in 0..9) 
      println([N,num_derangements=num_derangements(N), subfactorial=subfactorial(N), subfactorial2=subfactorial2(N)])
   end,
   println(["!20", subfactorial(20)]),
   println(["!20 approx", subfactorial2(20)]),
   println([subfactorial(N) : N in 0..30 ]),
   println([subfactorial2(N) : N in 0..30 ]),
   println(["!200", subfactorial(200)]),
   nl,
   println("Syntax sugar:"),
   println("'!'(20)"='!'(20)),
   println("20.'!'()"=200.'!'()),
   println("'!!'(20)"='!!'(20)),
   println("'!-!!'(10)"='!-!!'(10)),
   nl.

go2 => 
  garbage_collect(200_000_000),
  foreach(N in 0..5) 
     All=findall(L, (member(L,permutations(1..N)),nofixpoint(L))),
     println(N=All)
  end,
  nl.

num_derangements(N) = derangements(N).length.

derangements(N) = D =>
  D = [P : P in permutations(1..N), nofixpoint(P)].

table
subfactorial(0) = 1.
subfactorial(1) = 0.
subfactorial(N) = (N-1)*(subfactorial(N-1)+subfactorial(N-2)).


% approximate version of subfactorial
subfactorial2(0) = 1.
subfactorial2(N) = floor(1.0*floor(factorial(N)/2.71828 + 1/2.0)).

fact(N) = F =>
   F1 = 1,
   foreach(I in 1..N)
     F1 := F1 * I
   end,
   F = F1.

nofixpoint(L) =>
   foreach(I in 1..L.length)
     L[I] != I
   end.

% Some syntax sugar. Note the function must be an atom.
'!'(N) = fact(N).
'!!'(N) = subfactorial(N).


'!-!!'(N) = fact(N) - subfactorial(N).