### How would you have done this?

Make a program to create a permutated index for a given input. For information on what a permutated index is see this thread: http://www.cplusplus.com/forum/beginner/73297/

So I finished my version of this, but feel like I did it in-efficiently, or it could be done a better way. Now I want to see how others would have done it. It'd be awesome if you wanted to take the time to code it all out, but if you don't then just give a summary of how you would do it. If giving a summary answer the following points (Because it is easy to leave important stuff out or over-simplify something when summarizing):
1) How would you grab input?
2) How would you store the index?
3) How would you rotate, alphabetize, and then unrotate?
For reference, all the book (accelerated c++) has taught up to this point is stl List and Vector, references, looping, other basics. But use whatever methods you think would work best! I just want to see different ways of solving this.

Here is my attempt at it. I figured that instead of unrotating by comparing to a set string each time, which would be hard when the user can enter many strings for one go through, it'd be easier to store the times the line had been rotated. I did this through a structure that contains a list of strings (the words of the line) and an int to keep track of the times that line had been rotated. The code (is hopefully) self explanatory:
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127`` ``````#include #include #include #include using std::list; using std::string; using std::getline; using std::cin; using std::cout; // struct to hold a line of input split into words, and the number of times it's been rotated. struct indexLine { list LineWords; int timesRotated; }; list getWords(const string& line); // used to split the string line into a list containing the words string mergeWords(const list& words); // combines a list of a lines words into one string bool compare(const indexLine& line1, const indexLine& line2); // predicate used for alphabetizing indexLine structures int main() { list inputLines; string inputBuffer; indexLine currentLine; cout << "Enter EOF on a new line to end input\n"; while (getline(cin, inputBuffer)) { currentLine.LineWords = getWords(inputBuffer); currentLine.timesRotated = 0; inputLines.push_back(currentLine); } // store all possible line rotations in indexContextLines list indexContextLines; for (list::const_iterator structItr = inputLines.begin(); structItr != inputLines.end(); ++structItr) { currentLine = *structItr; for (list::size_type stringSizeCounter = 0; stringSizeCounter < structItr->LineWords.size(); ++stringSizeCounter) { currentLine.LineWords.push_back(currentLine.LineWords.front()); currentLine.LineWords.pop_front(); currentLine.timesRotated += 1; indexContextLines.push_back(currentLine); } } indexContextLines.sort(compare); // alphabetize // store the keyword (word that the line is sorted by) in indexKeyWords list indexKeyWords; for (list::const_iterator itr = indexContextLines.begin(); itr != indexContextLines.end(); ++itr) { indexKeyWords.push_back(itr->LineWords.front()); } // unrotate the lines, // note that if a line is rotated x times, where x is the number of words in it, then no unrotation is necessary for (list::iterator structItr = indexContextLines.begin(); structItr != indexContextLines.end(); ++structItr) { while ( structItr->timesRotated != structItr->LineWords.size() && structItr->timesRotated > 0) { structItr->LineWords.push_front(structItr->LineWords.back()); structItr->LineWords.pop_back(); structItr->timesRotated -= 1; } } //display permutated index list::iterator stringItr = indexKeyWords.begin(); for (list::iterator structItr = indexContextLines.begin(); structItr != indexContextLines.end(); ++structItr, ++stringItr) { cout << *stringItr << '\t' << mergeWords(structItr->LineWords) << std::endl; } return 0; } list getWords(const string& line) { list words; std::string::const_iterator itr = line.begin(); while (itr < line.end()) { if (isspace(*itr)) { ++itr;} else { string currentWord; while (itr < line.end() && !isspace(*itr)) { currentWord += *itr; ++itr; } words.push_back(currentWord); } } return words; } string mergeWords(const list& words) { string merged; for (list::const_iterator itr = words.begin(); itr != words.end(); ++itr) { merged += *itr + " "; } return merged; } bool compare(const indexLine& line1, const indexLine& line2) { string string1 = mergeWords(line1.LineWords); string string2 = mergeWords(line2.LineWords); for( string::const_iterator str1Itr = string1.begin(), str2Itr = string2.begin(); str1Itr != string1.end() && str2Itr != string2.end(); ++str1Itr, ++str2Itr ) { if( tolower( *str1Itr ) < tolower( *str2Itr ) ) { return true; } else if( tolower( *str1Itr ) > tolower( *str2Itr ) ) { return false; } } if( string1.size() < string2.size() ) { return true; } else { return false; } }``````

And a test run (the 3 lines after the first line are user input):
 ```Enter EOF on a new line to end input The quick brown fox jumped over the fence ^Z brown The quick brown fox fence jumped over the fence fox The quick brown fox jumped jumped over the fence over jumped over the fence quick The quick brown fox the jumped over the fence The The quick brown fox Press any key to continue... ```
Noooooo! Permuted index returns!

I'll take a look at this a little later when I finish work if I get the chance. :-)
lol...It was harder than it looked at first glance. :P
Only bump I'll do. Critique my code! :)
Topic archived. No new replies allowed.