Numbers to Letters algorithm

This topic is 3738 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Hey all, I am trying to solve this algorithm and my brain is having a bit of trouble. Basically, I am trying to go from a number to a set of letters. 0-25 would be A-Z 26-51 would be AA-AZ 52-77 would be BA-BZ ... 676-701 would be ZA-ZZ 702-727 would be AAA-AAZ 728-753 would be ABA-ABZ etc, etc My initial thought was to basically figure out what power of 26 the values were under, but then the offset issue came up (basically, for AA-ZZ, we aren't starting over at 0, we are starting at 26) ... and now my brain hurts and I have a bunch of spaghetti code Any thoughts? Thanks, Corey

Share on other sites
std::string identifier(std::size_t count){	std::string letters = "abcdefghijklmnopqrstuvwxyz";	std::string result;	while (true)	{		result = letters.substr(count % 26, 1) + result;		count /= 26;		if (!count)		{			break;		}		--count;	}	return result;}

I just so happened to need the same thing myself a week ago.

Σnigma

Share on other sites
Gorgeous. Thank you sir!

Share on other sites
template< typename elem_type >int LetterValue( std::basic_string<elem_type> &str, unsigned long value ){    str.clear();        for( int length = 0; value; length++ )    {        str.append( 'A' + ( value % 26 ) );        value /= 26;    }        return length();}

Share on other sites
You may want to look into arithmetic coding if you want to extend this method to infinite precision numbers (and thus strings) in a practical manner. This is essentially a special-case of arithmetic coding except with fixed equal-weight codes. Frankly I find it fascinating that this can be made work (elegantly) with only fixed-precision arithmetic, although it actually took computer science decades to solve the problem and it's still a patent minefield..

Oh, and to let this number itself determine the length of the string then you need to extend the alphabet to 27 symbols by including a special terminator (e.g. use division and modulo by 27 and let the resulting zero end the string).

Share on other sites
In Layman's terms, it looks to me like a conversion from base-10 to base-26. Which is exactly what all the posted code is doing [smile] Just thought I'd point that out.

Share on other sites
Not quite. In base 26, A would be zero and AA would also be zero. In the required system, A is zero but AA is 26. I think you just need to subtract 1 from the leftmost digit or something.

Share on other sites
Thought I'd have a go at a couple of n-gram functions:

Iterative solution:
std::string ngram(unsigned int index){    const char * symbols = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";    const unsigned int size = 26;    std::string result;                     do    {        result.insert(0, &symbols[index % size], 1);    }    while ((index /= size)-- > 0);    return result;}

Recursive solution:
std::string & ngram(unsigned int index, std::string & result){    const char * symbols = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";    const unsigned int size = 26;    if (index > size)        ngram(index / size - 1, result);    return result += symbols[index % size];}

I'm rather liking the elegance of the latter one [smile]

Share on other sites
This is a somewhat interesting problem in that a "sub-optimal" solution may actually be best.

Main problem with this type of algorithms comes from the need to append characters at front, requiring either insertions, re-allocations or checking for overruns.

The length of resulting string turns out to be floor(log((count+1)(n-1)+1)/log(n)).

Calculating this would allow in-place construction of string, but even at best, evaluating the length would be expensive, if not suffer from inaccuracies.

This is an important observation because of latest std::string implementation (at least under MVC++), which reserves a small buffer (16 bytes, I believe, much more than even long long could produce) before performing any dynamic allocations.

While std::string is often considered clumsy or inefficient, it turns out that in this case, it's surprisingly efficient, and should be almost identical to passing char[16], possibly not even performing any extra allocations.

Share on other sites
Quote:
 Original post by Daggerbot *** Source Snippet Removed ***

1) Strings already know their length, so what are you hoping to gain by counting it manually and returning it?

2) I think you're going to need, at minimum, to static_cast the 'A' to instantiate the template for types other than char.

3) Like Kylotan said.

1. 1
2. 2
3. 3
4. 4
Rutin
11
5. 5

• 12
• 19
• 10
• 14
• 10
• Forum Statistics

• Total Topics
632666
• Total Posts
3007720
• Who's Online (See full list)

There are no registered users currently online

×