Thread: Question on permutated indices

  1. #1
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901

    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.
    Last edited by indigo0086; 05-04-2006 at 04:56 PM.

  2. #2
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    I take it you're as lost as I am...well I'll come back to this one later lol

  3. #3
    Registered User
    Join Date
    Nov 2001
    Posts
    1,348
    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

  4. #4
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    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. #5
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    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.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  6. #6
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    Thanks man, I'll study this solution when I get home, but I think I understand it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Alice....
    By Lurker in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 06-20-2005, 02:51 PM
  2. Debugging question
    By o_0 in forum C Programming
    Replies: 9
    Last Post: 10-10-2004, 05:51 PM
  3. Question about pointers #2
    By maxhavoc in forum C++ Programming
    Replies: 28
    Last Post: 06-21-2004, 12:52 PM
  4. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM
  5. Question, question!
    By oskilian in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 12-24-2001, 01:47 AM