# Question on permutated indices

• 05-04-2006
indigo0086
Question on permutated indices
I'm doing an example from the book which I have to create a permuted permute the index, the book says it takes a sentence (in this case two), ad this is the in/output

Code:

``` The quick brown fox jumped over the fence [b]output[b]       The quick  brown fox jumped over the  fence the quick brown  fox                   jumped over the fence etc.. ```
The algorithm in the book suggests I do two things which i have, which is extract the sentence and then make rotations, I did so with these functions

Code:

```#include "functions.h" #include <cctype> #include <sstream> using std::vector; using std::string; using std::istringstream; typedef vector<string>::size_type str_sz; vector<string> parse(const string& aStr) {     istringstream words(aStr);     string temp;     vector<string> parsed;         while(words >> temp)         parsed.push_back(temp);                   return parsed; } vector<string> rotations (const string& aStr) {         vector<string> parsed = parse(aStr);     str_sz words = parsed.size();         vector<string> permutations;        string final, first, temp;         permutations.push_back(aStr); //puts the first string from the start     temp = aStr;         //does nubmer of rotations as there are words(excluding  one for first sentence)     for(str_sz i = 0; i < words - 1; i++)      {         istringstream body(temp); //sets the sstream object to the temp string                 body >> first;  //holds the first word of the sstream                 while(body >> temp)             final += temp + " ";  //concatenates the rest of the sstream                 final += first;  //puts the first word at the end                 permutations.push_back(final);  //puts that rotation into                 temp = final;    //sets temp         final = "";      }      return permutations; }```
The first function just parses the words, I use that for the sake of getting the number of words so I can do a certain number of rotations. Now the second function gets the string into a istringstream and then gets the first word into a string variable, and the rest into another string variable, the concatenates the body with the first word to create one rotation and puts that into an array. It then creates a new istringstream with the string value of the last rotation. It works fine.

the next thing is to sort the rotations, which I assume is already done since I pushed them back in the array in the order I rotated them

then this is where I'm confused...it says I should "unrotate and write the permuted index, which involves finding the separator, putting the phrase back together, and writing it propperly formatted"

Maybe it's because I'm not familiar with what a permuted index is (though I understand the concept of permutations), that I'm having trouble with this. If someone could re-word it so I can wrap my head around what I am to do, it would be helpful.
• 05-04-2006
indigo0086
I take it you're as lost as I am...well I'll come back to this one later lol
• 05-04-2006
kuphryn
permutation needs closer look

Code:

```p(vec constant &a, vec &b, first index, first source, source size, skip index) { for (i = index; i < source size; ++first source) { if ((first source % source size) != skip index) b[i++] = a[first source % source size]; } } vector a, b; integer n = 0 for (i = 0; i < vector a size; ++i) { b[0] = a[i]; for (k = i + 1; n < vector a size minus 1; ++k, ++n) { p(a, b, 1, k % vector a size, vector a size, i); for (j = 0; j < vector a size; ++j) b[j] } n = 0; }```
Kuphryn
• 05-05-2006
indigo0086
hard to read that code, no comments, , declaration of some varialbes. I don't think that is what it's asking, it says

"A permuted index is one in which each pharse is indexed by every word in the phrase"

I just don't get how that is.
• 05-06-2006
SilentStrike
It seems to me that you want to solve a problem like this?

http://acm.uva.es/p/v1/123.html

I don't see how rotating your strings really helps you. I solved that problem using a fairly advanced but standard data structure called an stl multimap. If you want a solution without fancy data structures, I'd suggest this.

Make an "intermediate" vector of strings representing the unsorted index.

Code:

```For each line in the input     for each word in line         new_val = word + " " + line         insert new_val into intermediate```
For example, given your sample input
Code:

```The quick brown fox jumped over the fence```
Intermediate would become

Code:

```The The quick brown fox quick The quick brown fox brown The quick brown fox fox The quick brown fox jumped jumped over the fence over jumped over the fence the jumped over the fence fence jumped over the fence```
Now, sort intermediate lexicographically, but not the strings inside it.

Code:

```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```
Then it's just a matter of eliminating the first word from each string in intermediate, and formatting the output with the correct number of spaces. The indexed word will be the word in the beginning of the string.
• 05-08-2006
indigo0086
Thanks man, I'll study this solution when I get home, but I think I understand it.