Success_Machine
08-09-01, 12:39 PM
If 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!
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!