Toward an Extension of Efficient Algorithm to Solve Derangement Problems by Dynamic Programming Approach

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.