# Can anyone find a mapping from the set of all possible string to the natural numbers?

Can anyone find a map(injection) $h$ from the set of all possible strings $S^*$ to the natural numbers $\mathbb{N}$?

$$h : S^* \rightarrow \mathbb{N}$$

Assume $S$ is finite. I would prefer an efficient map.

There should be nice applications of this question for perfect hashing, right?

• You probably mean injection instead of map. Right? – xskxzr May 11 '18 at 14:01
• yes that's what I meant – pedroth May 11 '18 at 16:22
• Perfect hashing is supposed to significantly reduce the amount of information you need to keep for each key. If every possibly value has a unique hash, the hash function is definitely collision-free but you've wasted an enormous amount of space. – rici May 11 '18 at 17:42
• Yes I understand what you are saying @rici. Here I just wanted a nice way to compute hash of strings, then I could apply $h(x) \mod N$ to insert in my hash table – pedroth May 14 '18 at 10:22
• @pedroth: that won't work well with either of the injections proposed in david richerby's answer or the comment by pseudonym. – rici May 14 '18 at 13:45

Just pretend that your alphabet $S = \{0, \dots, s\}$ for some $s$ and then a string in $S^*$ is just a natural number written out in base $s+1$. There's the slight wrinkle that $0$, $00$, $000$, etc. are all representations of zero, but that's easily fixed by associating the string $x$ with the number whose base-$(s+1)$ representation is $1x$ (i.e., $x$ with a $1$ stuck on the front).
• Making an injective mapping if $S$ is countably infinite is not difficult. Denote the string $s = s_1 s_2 s_3 \ldots s_n$ where $s_i$ are positive integers. Then $h(s) = 2^{s_1} 3^{s_2} 5^{s_3} \cdots p_n^{s_n}$ where $p_i$ are the prime numbers. – Pseudonym May 11 '18 at 14:15
• @Pseudonym I guess you could post it as an answer anyway, since it works just fine for finite $S$, too. – David Richerby May 11 '18 at 14:35
• @pedroth Take $S = \{0, \dots, 9\}$ and the approach is essentially just "Oh, look -- a string in $S^*$ is already a number!" – David Richerby May 11 '18 at 16:31