# Thread: Question on permutated indices

1. ## 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. 2. I take it you're as lost as I am...well I'll come back to this one later lol 3. 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 = 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 4. 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. 5. 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. 6. Thanks man, I'll study this solution when I get home, but I think I understand it. Popular pages Recent additions 