This looks handy.
Given the retry-on-bad-word feature, I was sceptical of the no-collision claim -- but after looking at the JS source code, I'm confident it's correct.
For each number encoded, one character from the alphabet is "held back" to use as a delimiter (with the particular character chosen changing as each number is processed, presumably to make the output "look more random"). The very first character output is essentially a "free choice" that selects the initial permutation of the alphabet to use.
The algorithm is implemented as a function encodeNumbers() that calls toId() to encode each number, then checks for bad words and recurses with a new value of "increment" if it finds any. To prove correctness it's helpful to imagine an "in-between" function, tryEncodeNumbers(numbers, alphabet), which the outer encodeNumbers() calls in a loop to do most of its work (pseudocode):
function encodeNumbers(numbers) {
offset = sum(numbers)
do {
result = tryEncodeNumbers(numbers, permute(alphabet, offset + increment++))
} while (badWordIn(result))
return result
}
Here permute() is a function that permutes the characters in its first (string) argument according to its second (integer) argument in some arbitrary way.
The toId(num, alphabet) function, which simply encodes a single number using "digits" taken from the characters in the alphabet parameter, is clearly injective with respect to the num parameter provided that alphabet contains no duplicate characters -- that is, if we hold some duplicate-free alphabet string fixed, every distinct value of num produces a distinct encoded string as output. (For example, toId(42, "0123456789") gives "42", and no other value of num produces this string when the alphabet remains unchanged.) tryEncodeNumbers(numbers, alphabet) first outputs a character representing alphabet (i.e., its initial alphabet -- which is its complete internal state), then joins together a bunch of these toId()-encoded numbers, with an extra character in between each that is known not to appear as a digit in the preceding number, permuting the alphabet in an alphabet-dependent but num-independent way for each encoded number output. Because the alphabet permutation is independent of the input array of numbers, this means that the alphabet used to encode the i-th number depends only on the initial alphabet and i. This means that, again holding its initial alphabet fixed, tryEncodeNumbers() is likewise injective with respect to the input array of numbers. (Suppose it were not: Then there is an initial dupe-free alphabet, and two distinct arrays of numbers, that produce the same output. Find the first position where the two arrays differ. Since the final results are identical by assumption, one of the two encoded outputs for this position must be a prefix of the other. But if the two encoded outputs are of different lengths, the shorter one must either terminate the entire string, making it shorter than the other encoded string, or be immediately followed by a character that cannot appear in the output of toId() with the alphabet used at this position, both of which contradict the assumption that the resulting strings are equal. Therefore toId() must have output identical strings for the two different numbers at this position, when given the same alphabet. But this contradicts injectivity of toId(), so this (non-injectivity of tryEncodeNumbers()) is impossible.)
The final step is to see that, if encoding two inputs with the top-level encodeNumbers() function gives the same first character C, it must be because the first successful (bad-word-free) loop iteration for the first input passed the same alphabet to tryEncodeNumbers() as the first successful loop iteration for the second input. If the remainders of the two encoded strings are also equal, then by injectivity of tryEncodeNumbers() for fixed alphabet choice their input number arrays must have also been the same. Since no restrictions were placed on the two inputs, this holds for all possible input pairs -- that is, it is impossible for encodeNumbers() to produce the same encoded output string for two different inputs.