COMBINATION GENERATION DEVICE, SOLVING SYSTEM FOR COMBINATION OPTIMIZATION PROBLEM, AND METHOD AND PROGRAM THEREFOR

摘要

Provided is a combination generation system wherein the increase of calculation time for an addition process, a shift process, and a comparison process which accompany the combination generation, caused by the increase of digits, is small. The combination generation device comprises a bit position acquisition means to obtain an inversion bit position which is a position of a bit to perform inversion, and a shift bit position which is a position of a bit which is to be shifted to the least significant bit, from an input bit array, on the basis of a predetermined reference, and to obtain a shift width required to shift the bit at the shift bit position to the least significant bit; a bit inversion means to invert a bit value at the inversion bit position of the input bit array obtained by the bit position acquisition means, and to invert a bit value at the position one bit lower therethan; and a bit shift means to shift all bits located at positions two or more bits lower than the inversion bit position in the bit array which has been inverted by the bit inversion means, by the shift width obtained by the bit position acquisition means.