Permutating

[mitrious]

The execise in the books asks this:

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.

And says:

A good algorithm is suggested in The AWK Programming Language by Aho, Kernighan, and
Weinberger (Addison-Wesley, 1988). That solution divides the problem into three steps:
Read each line of the input and generate a set of rotations of that line. Each rotation
puts the next word of the input in the first position and rotates the previous first word
1.
to the end of the phrase. So the output of this phase for the first line of our input would
be
The quick brown fox
quick brown fox The
brown fox The quick
fox The quick brown
Of course, it will be important to know where the original phrase ends and where the
rotated beginning begins.
2. Sort the rotations.
Unrotate and write the permuted index, which involves finding the separator, putting
the phrase back together, and writing it properly formatted.

I didn't quite understand his suggestion...

Look what I did ( it works fine I think)

any hints? what exactly is he suggesting there?

#include "Split.h"
#include <iostream>
#include <vector>
#include <string>

using std::cout;		using std::endl;
using std::cin;			using std::vector;
using std::string;

vector<string> permute(const vector<string>& s)
{
	vector<string> ret = s;
	typedef vector<string>::size_type vec_sz;
	ret.push_back(s[0]);
	ret.erase(ret.begin());
	return ret;
}

string display(const vector<string>& s)
{
	string rec;

	for(vector<string>::const_iterator it = s.begin();
		it != s.end(); ++it){
			rec += *it + " ";
	}

	return rec;
}


int main()
{
	cout << "Enter the phrase you wish to permute: ";

	string phrase;

	while(getline(cin, phrase)){
		vector<string> p = split(phrase);

		for(vector<string>::size_type i = 1; i != p.size(); ++i){
			if(i == 1)
				cout << display(p) << endl;
			
		p = permute(p);
		cout << display(p) << endl;
		}
	}
	return 0;
}

here's the function I used called Split

#include "Split.h"

#include<algorithm>
#include<cctype>

using std::string;	using std::vector;
using std::isspace;	using std::sort;

vector<string> split(const string& s)
{
	vector<string> rec;
	typedef string::size_type string_sz;
	string_sz i = 0;

	while(i != s.size()){

		while(i != s.size() && isspace(s[i]))
			++i;

		string_sz j = i;

		while(j != s.size() && !isspace(s[j]))
			++j;
		if(i != j){
			rec.push_back(s.substr(i, j - i));
			i = j;
		}
	}
	return rec;
}