Ranking alphabets
Hi, I'd like to ask if there is an efficient way to rank an alphanumberic word based on its ASCII number, and to place it in a vector?
For example:
m a t c h m a k e r
7 1 10 3 5 8 2 6 4 9
For example:
m a t c h m a k e r
7 1 10 3 5 8 2 6 4 9
closed account (Dy7SLyTq)
im not quite sure what your asking, but if i understand you correctly, then what you want is to have a hash algorithim. then if you dont need to do direct lookup (ie with a vector) i would use a linked list for speed. you can either use <list> from the stl or write your own
Correct me if I'm wrong, but this is what I think you're trying to do.
You're trying to take a word (say, "matchmaker"), sort the letters ("aacehkmmrt"), and then output the new position of each letter in the original word? (e.g. the first 'm' ended up as the 7th letter, the 'a' after that ended up as the 1st letter, etc.)
If that's the case, then here's what you can do.
First, number off the letters of the original word:
Then, sort the word, moving the numbers along with the letters:
Then, for each i from 1 to the size of the word, take the number ki associated with the ith letter of the new (sorted) word and assign the value i to the kith letter of the original word.
For instance, the 4th letter of the sorted word is 'e', which has a value of 9. So take the 9th letter of the original word (which, of course, is 'e') and assign that a value of 4.
Does that make sense?
As for keeping track of the numbers along with the letters, you have a few options:
1) Keep two std::vectors, one for letters and one for numbers.
Implement your own sort function that takes both as input, and whenever you would swap two letters in the sorting process, also swap the corresponding numbers in the other vector.
2) Keep one std::vector of std::pairs of letters and numbers.
Implement your own sort function that just looks at the letters when sorting.
3) Same as #2, except use std::sort with a custom compare function instead of implementing your own sorting function.
You're trying to take a word (say, "matchmaker"), sort the letters ("aacehkmmrt"), and then output the new position of each letter in the original word? (e.g. the first 'm' ended up as the 7th letter, the 'a' after that ended up as the 1st letter, etc.)
If that's the case, then here's what you can do.
First, number off the letters of the original word:
m a t c h m a k e r 1 2 3 4 5 6 7 8 9 10 |
Then, sort the word, moving the numbers along with the letters:
a a c e h k m m r t 2 7 4 9 5 8 1 6 10 3 |
Then, for each i from 1 to the size of the word, take the number ki associated with the ith letter of the new (sorted) word and assign the value i to the kith letter of the original word.
For instance, the 4th letter of the sorted word is 'e', which has a value of 9. So take the 9th letter of the original word (which, of course, is 'e') and assign that a value of 4.
Does that make sense?
As for keeping track of the numbers along with the letters, you have a few options:
1) Keep two std::vectors, one for letters and one for numbers.
Implement your own sort function that takes both as input, and whenever you would swap two letters in the sorting process, also swap the corresponding numbers in the other vector.
2) Keep one std::vector of std::pairs of letters and numbers.
Implement your own sort function that just looks at the letters when sorting.
3) Same as #2, except use std::sort with a custom compare function instead of implementing your own sorting function.
As DTS suggested, you probably want to hash the string. Here is a website that introduces hashing:
http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
Another method of hashing that looks very promising is this:
http://stackoverflow.com/a/10745675/2089675
After reading the first link you should be familiar with the word avalanche. I think the second link could produce avalanche without requiring to much space
http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
Another method of hashing that looks very promising is this:
http://stackoverflow.com/a/10745675/2089675
After reading the first link you should be familiar with the word avalanche. I think the second link could produce avalanche without requiring to much space
Last edited on
Topic archived. No new replies allowed.