0
Ball In A Box Productions
Lexicographical indexing applies a numerical value to a list of items which do not increment uniformly. While usually applied to dictionaries or other lexicons, there is no algorithm to automate the indexing process. For example, this short list of words:100 Tall
101 Tame
102 Tan
103 Tap
104 Tar
The two words missing from the list, Tao and Taq, do not interfere with the index. However, this cannot be mathematically derived as a computer would consider the two missing words as valid character combinations.
A normal number counter, or odometer, contains the digits 0 to 9 and will increment according to a natural number sequence. The current state of the counter is equivalent to the index of that number.
With the case of an ascending order, unique number counter, indexing becomes more complicated as shown in the following example:
00: 01234
01: 01235
02: 01236
03: 01245 (01240 01241 01242 01243 01244)
04: 01246
05: 01256
06: 01345
07: 01346
08: 01356
09: 01456
10: 02345
Index 03 shows the least significant digit reaching a maximum value of 6 before being reset to 5 with the next highest value incrementing only once. All the invalid values are show in brackets.
Normally a set of nested loops would be the optimal method to count all combinations of ordered unique sets until the set being sought was reached. The count is the actual index of that set.
It is possible to calculate the index of any set by consulting a chart of predefined values for a specific set of numbers. By recording the current index for each digit in the set, as it is incremented, (except for the right most digit) allows for addition to calculate the index.
The set indexed as 03 is the first time the fourth digit is incremented; from 3 to 4. The digit to the right had incremented twice before expiring. But that digit must be unique in the set and higher than the digit to the left.
When the third digit is incremented at index 06, the 4th digit had incremented twice through 6 iterations of the index. Knowing how many indexes were required for each digit to the right to expire allows the current index to be computed.
LexiChart.exe generates charts for all possible sets with a lexicographical index less than 4,294,967,296 as this is the highest number a double word assembly register can hold. However, the chart concept is not limited to 32 bit calculations should extremely large sets be required; a competent programmer should be able to easily create suitable software to handle double precision variables.
In addition to chart creation, lexichart.exe also offers single and multiple set to index calculations should there ever be a need.
More