Toward an Extension of Efficient Algorithm to Solve Derangement Problems by Dynamic Programming Approach
3
Issued Date
2024-03-01
Resource Type
ISSN
10765204
Scopus ID
2-s2.0-85189312961
Journal Title
International Journal of Computers and their Applications
Volume
31
Issue
1
Start Page
5
End Page
14
Rights Holder(s)
SCOPUS
Bibliographic Citation
International Journal of Computers and their Applications Vol.31 No.1 (2024) , 5-14
Suggested Citation
PatanasakPinyo T., Sulaiman A. Toward an Extension of Efficient Algorithm to Solve Derangement Problems by Dynamic Programming Approach. International Journal of Computers and their Applications Vol.31 No.1 (2024) , 5-14. 14. Retrieved from: https://repository.li.mahidol.ac.th/handle/123456789/97916
Title
Toward an Extension of Efficient Algorithm to Solve Derangement Problems by Dynamic Programming Approach
Author(s)
Author's Affiliation
Corresponding Author(s)
Other Contributor(s)
Abstract
In statistics, probability theory, and computer science, a derangement, ln, is known to be a basic problem that computes total ways of rearranging n ∈ N items such that a result contains no item i that stands in the same position as it did in the input. Formally, the derangement problem has a problem instance of a finite collection (Formula Presented). With this formulation, ln is a total number of qualified collections where contains n members of (x1,yj) where i ≠ j and every x1 and yj (1 ≤ i,j ≤ n) must show up exactly once in b'. In this article, we present a dynamic programming algorithm that computes ln and its justification. We also provide a discussion about extending the limitation of the problem with an objective to cover a general case where we have a finite set of variables a1,a2,.…,ak rather than the traditional scenario that has only two variables: X and y.