It is not unlikely that what I want to do is not possible, but it doesn't hurt to ask.
Imagine a set of lists, each containing positive integers (in my case, a list always consists of four integers, but that shouldn't make any difference).
a = [35, 2, 123684, 647]
b = [453, 346457546457, 6, 0]
c = ...
Then there is an alphabet, e.g.
alphabet = [A, .., Z, a, .., z, 0, .., 9]
What I want to do is to create a function that transforms the lists into strings using the alphabet.
f: (list[Int], alphabet) -> string
The requirements for f are as follows:
f should be injective in the sense that two different lists always result in two different strings and one specific list always results in the same string each time f is called.
Notes:
- Two lists are equal if both contain the same elements in the same order.
- It is ok if transformations of different lists using different alphabets result in the same string. The unique-requirement only applies to the transformation of different lists using the same alphabet.
- An inverse function is not required.
- Now the hard part: the resulting strings must be as short as possible.
All of the numbers are 32 bit integers. But the fact that they vary greatly in size (the possible range is from 0 to Int.max
) should be taken into account. Just chaining the 32 bit representations together (or doing something else that uses chunks of a fixed size) is not a viable solution.
One approach could be to choose one character of the alphabet and use it as a separator. This is basically what hashids does. E.g. if 'A' is the separator, all resulting strings would look like this: "...A...A...A..."
.
What I don't like about this solution:
- The effective size of the alphabet is reduced by one, since one of the characters can only be used as a separator, not for encoding numbers. This results in longer strings, especially when using small alphabets
- The separatoritself also extends the string. Encoding a list of four integers means three additional characters in the result.
I'm wondering if there is a less obvious solution to the problem, maybe a more mathematical approach? Essentially, the problem is to "merge" multiple numbers into a single (unique) number.