Alternative Approach to Achieve a Solution of Derangement Problems by Dynamic Programming
Issued Date
2023-01-01
Resource Type
eISSN
23987340
DOI
Scopus ID
2-s2.0-85152628148
Journal Title
EPiC Series in Computing
Volume
91
Start Page
98
End Page
107
Rights Holder(s)
SCOPUS
Bibliographic Citation
EPiC Series in Computing Vol.91 (2023) , 98-107
Suggested Citation
Patanasakpinyo T., Sulaiman A. Alternative Approach to Achieve a Solution of Derangement Problems by Dynamic Programming. EPiC Series in Computing Vol.91 (2023) , 98-107. 107. doi:10.29007/1j3g Retrieved from: https://repository.li.mahidol.ac.th/handle/123456789/82651
Title
Alternative Approach to Achieve a Solution of Derangement Problems by Dynamic Programming
Author(s)
Author's Affiliation
Other Contributor(s)
Abstract
Derangement is one well-known problem in the filed of probability theory. An instance of a derangement problem contains a finite collection C of n paired objects, C = {(x1, y1), …, (xn, yn)}. The derangement problem asks how many ways to generate a new collection C′ ≠ C such that for each (xi, yj ) ∈ C′, i ≠ j. We propose an efficient dynamic programming algorithm that divides an instance of the derangement problem into several subproblems. During a recursive process of unrolling a subproblem, there exists a repeated procedure that allows us to make a use of a subsolution that has already been computed. We present the methodology to formulate a concept of this subproblem as well as parts of designing and analyzing an efficiency of the proposed algorithm.