NON-DECREASING SEQUENCE DETERMINING DEVICE, NON-DECREASING SEQUENCE DETERMINING METHOD, AND PROGRAM

摘要

The present invention efficiently determines the presence of a non-decreasing sequence. An aligning unit (10) generates vectors t_i,i+1 and b_i,i+1 wherein the elements of a set P_i have been arranged in ascending order. A merging unit (20) iterates a process wherein vectors (t_i,j,b_i,j) and (t_j,k,b_j,k) are merged so as to generate a vector (t_i,k,b_i,k) and thereby generates vectors t_0,m and b_0,m. A stable sorting unit (21) generates a vector e wherein vectors b_i,j and t_j,k have been concatenated and stable sorted. A searching unit (22) searches the tuple (λ,x,y) for which e[λ]is b_i,j[x] and e[λ+1] is t_j,k[y] and generates a set X that includes every x and a set Y that includes every y. An extracting unit (23) generates a vector t_i,k wherein t_i,j[x] (x∈X) has been arranged in ascending order and a vector b_i,k wherein b_j,k[y] (y∈Y) has been arranged in ascending order. A determining unit (30) outputs determination results that indicate that a non-decreasing sequence is not present if the length of the vector t_0,m is 0.