How to resolve the algorithm Permutations/Derangements step by step in the Picat programming language

Published on 12 May 2024 09:40 PM
#Picat

How to resolve the algorithm Permutations/Derangements step by step in the Picat programming language

Table of Contents

Problem Statement

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.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Permutations/Derangements step by step in the Picat programming language

Source code in the picat programming language

import util.

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("subfactorial0..30"=[subfactorial(N) : N in 0..30 ]),
   println("subfactorial2_0..30"=[subfactorial2(N) : N in 0..30 ]),
   println(["!200", subfactorial(200)]),
   nl,
   println("Syntax sugar:"),
   println("'!'(20)"='!'(20)),
   println("200.'!'()"=200.'!'()),
   println("'!!'(20)"='!!'(20)),
   println("'!-!!'(10)"='!-!!'(10)),
   nl.

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

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

% subfactorial: tabled recursive function
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)).

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

% No fixpoint in L
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).

You may also check:How to resolve the algorithm Queue/Definition step by step in the ALGOL W programming language
You may also check:How to resolve the algorithm Find common directory path step by step in the PowerBASIC programming language
You may also check:How to resolve the algorithm Literals/Integer step by step in the Maxima programming language
You may also check:How to resolve the algorithm Empty program step by step in the Batch File programming language
You may also check:How to resolve the algorithm The Twelve Days of Christmas step by step in the MAD programming language