I have a database that contains many categories with each category associated with an ID number. I am looking for a method to assign ID numbers to the categories where if you were to add any of the assigned ID numbers together, it would create a unique sum. In turn, that unique sum could be used to go backwards and identify which categories were added together. It should not be limited to just two elements summed together as well; it would be 2, 3...n elements summed together. For example, if I summed four category ID numbers together, that sum would be unique to that combination of four categories only; no other combination of categories, four or otherwise, would result in the same sum.
An applied example of this could be a list or table of races. Each race would have an ID number associated with it. If a person identified themselves as being more than one race, e.g. white and black (two races), or white, black, and Asian (three races), then the sum of the IDs would be a unique number such that the sum would only be associated with that specific combination of races. You could then reference that summed number as a code value for a multi-racial description that could be printed on a report or something.
Is there a mathematical term for this?
Is there a formula one could use to create the ID numbers that would cause this result?
And finally, if presented with a number, what would be the most efficient way to breakdown the number to determine which elements were summed together assuming you had the list of constituent category IDs?
CodePudding user response:
I would actually handle this through concatenating strings rather than adding numbers. For instance, if you had three races, with IDs of 1, 2, and 3, and you wanted to identify someone who picked all three, I would have an ID of "123". Of course, if you're just using numbers, then you can just add an extra zero to each table, so the first ID would be 1, the second would be 20, and the third would be 300. But, again, if you used string concatenation you could have IDs that were more than just numbers.
CodePudding user response:
The smallest such series of integers are the powers of 2:
1, 2, 4, 8, 16, 32, 64, 128, 256...
No two different subsets of this series have the same sum - this is why the binary numeral system works. Note that this is equivalent to using the bits of an integer as a set data structure, normally called a bitset or bit array.
To determine the individual elements which make up a sum, you can use the bitwise &
operator to test whether each individual bit is a 1 or a 0 (indicating whether that element is present or absent, respectively).