### Update

Since I originally wrote this blog post, I have discovered an even better solution which satisfies a new fifth condition I didn’t think was achievable. If you already read this blog post pre-update, skip ahead to the last section to see the new solution.

### Required conditions

The bit-shift solution was inspired by this Stackoverflow post.

Note:The solution linked above does not establish nor require the between-integers size-ordering constraint like this blog post does, but instead, hardcodes a maximum integer size ahead of time. Use whichever solution is more suitable for you.

Let’s say you have three positive integers (not including zero, but you can easily add one to the integers to handle that case), labelled `a`, `b`, & `c`, where these integers follow a size-ordering constraint of `c >= b >= a`

. You want to identify these three integers by a single integer identifier which satisfies four conditions:

- The ID is unique to the three integers.
- If put in a list or table, the ID is in the same relative position as the three integers would be.
`1-1-1`

comes before`2-1-1`

, which comes before`2-2-1`

, etc.

- The ID is a reasonably small number that is suitable to be used as a key.
- The ID is relatively easy to compute, or at least faster than a typical hash function.
- (Optional) If put in a list or table, the IDs leave no gaps or unused integers.
- If this is a requirement for you, see the last solution.

### Prime-based solution

To demonstrate what the three-to-one conversion actually looks like in practice, here’s what computing `2^c * 3^b * 5^a`

as the ID gives you:

Unfortunately, this only satisfies the first of the outlined conditions, as these IDs don’t preserve order, they grow in size really quickly, and the ID is increasingly difficult to compute the greater the three integers get.

As it turns out however, the idea of using exponents, and specifically two to the power of some other number, is heading in the right direction…

### Bit-shift solution

To cut to the chase, here’s a Lua script that demonstrates this solution:

To test that this works, swap the

`./script.lua | sort -cn`

to test the ordering and`./script.lua | sort -n | uniq -d`

to test that the IDs never repeat.

#### Explanation

The `<<`

syntax in Lua means we’re performing a left bit-shift operation, where all the bits in a given sequence are moved to the left. For instance, doing one left bit-shift on the bit sequence `00000001`

would yield `00000010`

, which is the same operation as performing `integer * 2^shift`

(in other words, each left bit-shift doubles the number).

If bit-shifting is unavailable to you, you could do

`b * 2^bits`

&`c * 2^(bits * 2)`

instead, however, remember that math operations are slower than bit manipulation, even if both yield the same answers in nearly all cases.

The `math.ceil(math.log(c, 2))`

line computes the minimum number of bits needed to represent the largest integer we’ve been given, which because of the size condition of `c >= b >= a`

is always the value of the integer `c`.

Left bit-shifting `b` by `bits` bits, `c` by `bits * 2`

bits, and adding them to integer `a` forms a new bit string where each integer is allocated its own non-overlapping range (e.g. `2-1-1`

is the bit string `10 01 01`

). More simply, the three integers have been concatenated together as binary.

Naturally then, if concatenating the three integers into a string satisfies the uniqueness and ordering properties, as said string is literally what the script prints beside each ID to test if their unique and ordered, then interpreting the computed bit string as an integer will always yield an integer which itself is unique and preserves the same ordering.

#### …And more?

Ah right, another nice property of the bit-shifting solution is that it can be generalised to any number of integers; all it takes to find the ID for four integers (where `d >= c >= b >= a`

) is to amend the ID formula to be written as:

```
bits = math.ceil(math.log(d, 2))
ra = a
rb = b << bits
rc = c << bits * 2
rd = d << bits * 3
id = ra + rb + rc + rd
```

### Triangular & tetrahedral numbers solution

In an ideal world, the tuple-to-ID conversion would leave no gaps between ID values, like this:

Fortunately, the `c >= b >= a`

size condition allows us to do exactly this. Here’s a solution which uses triangular & tetrahedral number sequence formulas to find unique, ordered, and gapless ID values:

Like the bit-shift solution, this can be extended to include more integers, assuming a similar size constraint such as `d >= c >= b >= a`

, by including equivalent formulas for higher dimensional shapes. For a fourth number, `d`

, you would include the pentatope number sequence formula.