Numbers to Letters algorithm
Author
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
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
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();}
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).
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).
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.
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.
Thought I'd have a go at a couple of n-gram functions:
Iterative solution:
Recursive solution:
I'm rather liking the elegance of the latter one [smile]
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]
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
