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

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Permutations/Derangements step by step in the EchoLisp 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 EchoLisp programming language

Source code in the echolisp programming language

(lib 'list) ;; in-permutations
(lib 'bigint)

;; generates derangements by filtering out permutations
(define (derangement? nums) ;; predicate
    (for/and ((n nums) (i (length nums))) (!= n i)))

(define (derangements n)
    (for/list ((p (in-permutations n))) #:when (derangement? p) p))

(define (count-derangements n)
    (for/sum ((p (in-permutations n))) #:when (derangement? p) 1))

;;
;;  !n = (n - 1) (!(n-1) + !(n-2)) 

(define (!n n)   
	(* (1- n) (+ (!n (1- n)) (!n (- n 2)))))
(remember '!n #(1 0))


(derangements 4)
    → ((3 0 1 2) (2 0 3 1) (2 3 0 1) (3 2 0 1) (3 2 1 0) (2 3 1 0) (1 2 3 0) (1 3 0 2) (1 0 3 2))

;; generated versus computed

(for ((i 10)) (writeln i '| (count-derangements i) (!n i)))

0     |     1     1    
1     |     0     0    
2     |     1     1    
3     |     2     2    
4     |     9     9    
5     |     44     44    
6     |     265     265    
7     |     1854     1854    
8     |     14833     14833    
9     |     133496     133496    

(!n 20)
    → 895014631192902121


  

You may also check:How to resolve the algorithm Tau function step by step in the BASIC programming language
You may also check:How to resolve the algorithm Hello world/Web server step by step in the min programming language
You may also check:How to resolve the algorithm Binary digits step by step in the Oforth programming language
You may also check:How to resolve the algorithm Null object step by step in the Scala programming language
You may also check:How to resolve the algorithm Terminal control/Hiding the cursor step by step in the Scala programming language