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

摘要

Determination as to whether a nondecreasing sequence exists or not is efficiently made. A sorting part 10 sorts elements of a set P_i in ascending order to generate vectors t_i,i+1 and b_i,i+1. A merging part 20 generates vectors t_0,m and b_0,m by repeating the process of merging vectors (t_i,j, b_i,j) and (t_j,k, b_j,k) to generate (t_i,k, b_i,k). A stable-sorting part 21 generates a vector e by coupling and stably sorting vectors b_i,j and t_j,k. A searching part 22 searches for sets of (λ, x, y) in which e[λ] is b_i,j[x] and e[λ + 1] is t_j,k[y] and generates a set X including all x and a set Y including all y. An extracting part 23 sorts t_i,j[x] (x ∈ X) in ascending order to generate a vector t_i,k and sorts b_j,k[y] (y ∈ Y) in ascending order to generate a vector b_j,k. If the length of a vector t_0,m is 0, a determining part 30 outputs a result of determination that indicates the absence of a nondecreasing sequence.