5 replies to this topic

[IsNe]

Hey, at the moment i am reading the book "Accelerated C++" and have come across this exercise:

5-1. Design and implement a program to produce a permuted index.
A permuted index is one in which each phrase is indexed by every word in the phrase

So far i have been able to write these functions in the program:
A: Collects user input
B: Rotates the sentence
input:
- hello there IsNe
output:
- there IsNe hello
- IsNe hello there
C: Alphabetised the different rotations of all the inputted sentences

what i need help/suggestions for is a function(s) that will
A: Rotate it back
B: output the whole original sentence alphabetical
The above example would turn out like this:
-----------hello there IsNe---
hello there IsNe----------------
------hello there IsNe---------

[IsNe]

#include <iostream>
#include <vector>
#include <string>

using std::cout;    using std::cin;
using std::string;  using std::endl;
using std::vector;  using std::istream;
typedef vector<string>::size_type vec_sz;
typedef string::size_type string_sz;

//Get user input
istream& getInput(istream& in, vector<string>& input)
{
    string ret;

    while (getline(in, ret))
        input.push_back(ret);

    in.clear();

    return in;
}

// Split up the strings into single words for use in rotating the sentence
vector<string> split(const string& sentence)
{
    vector<string> ret;

    string_sz j = 0;
    while (j != sentence.size())
    {
        while (j != sentence.size() && isspace(sentence[j]))
        j++;

        string_sz y = j;
        while (y != sentence.size() && !isspace(sentence[y]))
        y++;

        if (j != y)
        ret.push_back(sentence.substr(j, y-j));

        j = y;
    }

    return ret;
}


// Rotate input before alphabetizing
vector<string> rot(const string& inputString)
{
    // Split it into words before rotating
    vector<string> words = split(inputString);


    vector<string> ret;

    if (words.size() != 0)
    {
        for (vec_sz i = 0; i != words.size(); i++)
        {
            string connect;


            for (vec_sz j = i; j != (words.size() + i); j++)
            {
                if (j < words.size())
                connect += words[j] + ' ';
                else
                connect += words[j - words.size()] + ' ';
            }
            ret.push_back(connect);

        }
    }
    return ret;
}

bool compare(const string& x, const string& y)
{
    return x < y;
}

int main()
{
    // Get user input
    vector<string> input;
    getInput(cin, input);

    // Vector to store the rotated lines in
    vector<string> rotInput;

    // Input the rotated combinations into rotInput
    for (vec_sz i = 0; i != input.size(); i++)
    {
        vector<string> insertRot = rot(input[i]);

        if (i == 0)
            rotInput = insertRot;
        else
            rotInput.insert(rotInput.end(), insertRot.begin(), insertRot.end());
    }

    sort(rotInput.begin(), rotInput.end(), compare);

    for (vec_sz i = 0; i != rotInput.size(); i++)
    cout << rotInput[i] << endl;


    return 0;
}

[JCoder]

WTF? This should be doable in 5 lines of code...

[IsNe]

really? xD

[JCoder]

1. create an empty multi map of type string -> string
2. for every phrase p (read from the input) do:
3. split it into words
4. for each word w do:
5. put (w -> p) into the multimap

Now the multimap contains a permuted index :)
If your language cannot do that in 5 lines, it is broken. Consider using a different one.

[IsNe]

well, part of the exercise is actually learning what I'm reading.
And by using the things i've read so far in the book i'm gonna make this program
haven't read about mutimaps and that stuff yet