1. Toward an Extension of Efficient Algorithm to Solve Derangement Problems by Dynamic Programming Approach.
- Author
-
Pinyo, Thitivatr Patanasak and Sulaiman, Adel
- Subjects
DYNAMIC programming ,PROBABILITY theory - Abstract
In statistics, probability theory, and computer science, a derangement, !n, 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 C = {(x
1 ,y1 ), .∙∙., (xn ,yn )}, ∣C∣ = n. With this formulation, !n is a total number of qualified collections C' where C' contains n members of (xi ,yj ) where i ≠ j and every Xi and yj (1 ≤ i,j < n) must show up exactly once in C'. In this article, we present a dynamic programming algorithm that computes !n 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. [ABSTRACT FROM AUTHOR]- Published
- 2024