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