SciForums.com > Life > Free Thoughts > Selecting Subsets From Huge Populations PDA View Full Version : Selecting Subsets From Huge Populations Post ReplyCreate New Thread Success_Machine08-09-01, 01:39 PMIf a problem consists of an enormous number of unique objects that have to be analyzed independantly, but there are so many objects that it would take millions of years to solve then the problem is known as "np-complete". It can be downsized by selecting a subset of the total. This is what is done in the real world. But how do you select a subset with a proper distribution? If you have n objects and want to select a subset of r objects from them, then you can choose C unique combinations of r objects. The number of unique combinations, C, is found as follows: C = n!/(r!(n-r)!) You can use a binary number scheme to represent each unique combination. The right-most "1" moves to the right until it reaches the end, and so on: .........Index.........Binary.....Decimal....... combination #1 = 1110000 = 224 combination #2 = 1101000 = 208 combination #3 = 1100100 = 200 combination #4 = 1100010 = 196 combination #5 = 1100001 = 194 combination #6 = 1011000 = 176 combination #7 = 1010100 = 168 combination #8 = 1010010 = 164 combination #9 = 1010001 = 162 combination #10 = 1001100 = 152 combination #11 = 1001010 = 148 . . . . . . etc. The columns represent "powers of 2". For example the rightmost column is equivalent to 2 raised to the power of 1. The column second from the right is equivalent to 2 raised to the power of 2, and so on. The leftmost column is equivalent to 2 raised to the power of n. To convert the binary combination to a number just add up all the powers of 2, but multiply each by the "1" or "0" found in that column of the combination. Note that the decimal representation provides a steadily decreasing column of numbers. This can be approximated by a polynomial equation. Once you know this equation you can enter any index number in, and get a decimal out. Then convert the decimal to binary representation. In this way you do not have to know the pattern inherent in the list of binary numbers. You can find any combination without knowing the previous combination. You can select every 10th combination without having to expend computational time deriving the previous binary patterns in a sequential manner. Have fun! Post ReplyCreate New Thread