Are there more strings than numbers?
Suppose (hypothetically) that you get this question during a round of technical/math interviews:
0 -> "dog"
1 -> "cat"
2 -> "IDONTKNOW"
3 -> "Infinity"
...
That's not a great strategy. Clearly you need some order on the right side of the mapping. But if we think about order, you may end up in a situation where you'll convince yourself that there are way more strings than natural numbers. Without loss of generalization, we'll assume only strings in the alphabet of the uppercase English letters. Suppose that you start mapping each number to a sequence of "A"s. Take a look at image below:
With this approach we have exhausted all the natural numbers (notice the Googleplex there) without even getting to reach the letter "B"! Is this a proof that there are more strings than natural numbers?
No. It isn't.
The right approach is to order the right side based on the length of the strings. Imagine a tree where the first level contains all the strings with length 1 (also known as 26^0), the second level contains all the strings with length 26 (also known as 26^1), and so on. That way we can create a 1-1 mapping between the natural numbers and the strings. Take a look at the image below:
What we have done then is to show that the cardinality of the natural numbers is the same as the cardinality of the set of the possible strings using all 26 letters. Crazy to think that these two sets (natural numbers and all possible strings) have the same size!
Of course, since this is a coding blog, we can't wrap it up without writing some code. If you want to write a function that given a number returns the corresponding string, for any number, just use the code below (the reverse is left as an exercise), which runs in O(Log26(N))-time.
Hence, for the input 10^100 (Googleplex), the corresponding unique string is this one:
Cheers & hugs!!! ACC.
"Create a 1-1 mapping
between the natural numbers
and every single
conceivable string"Wow. Well, you may pull up your sleeves and start thinking about it. Start randomly:
0 -> "dog"
1 -> "cat"
2 -> "IDONTKNOW"
3 -> "Infinity"
...
That's not a great strategy. Clearly you need some order on the right side of the mapping. But if we think about order, you may end up in a situation where you'll convince yourself that there are way more strings than natural numbers. Without loss of generalization, we'll assume only strings in the alphabet of the uppercase English letters. Suppose that you start mapping each number to a sequence of "A"s. Take a look at image below:
No. It isn't.
The right approach is to order the right side based on the length of the strings. Imagine a tree where the first level contains all the strings with length 1 (also known as 26^0), the second level contains all the strings with length 26 (also known as 26^1), and so on. That way we can create a 1-1 mapping between the natural numbers and the strings. Take a look at the image below:
Of course, since this is a coding blog, we can't wrap it up without writing some code. If you want to write a function that given a number returns the corresponding string, for any number, just use the code below (the reverse is left as an exercise), which runs in O(Log26(N))-time.
Hence, for the input 10^100 (Googleplex), the corresponding unique string is this one:
HXRTPLBMWAIWCQLZPMGLPZIAEGSDIVMBVLNSSUSBJTBCGYWAYCQNHXZTQWWIKXVRSPTAZPP
static string NumberToStringOneToOneMapping(BigInteger n)
{
string result = "";
while (n > 0)
{
result = ((char)(((n - 1) % 26) + (int)'A')).ToString() + result;
n = (n - 1) / 26;
}
return result;
}
Comments
Post a Comment