Can't get my head around this question.

[Kieth89]

The question deals with Permutated Index sorting. My book (Accelerated c++ by Andrew Koenig & Barbara Moo) explains it as follows:

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, given the following input

The quick brown fox
jumped over the fence

the output would be

The quick brown fox
jumped over the fence
The quick brown fox
jumped over the fence
jumped over the fence
The quick brown fox
jumped over the fence
The quick brown fox

(Note to Usenet readers: You need to use a constant-width font to read the
table above properly.)

A good algorithm is suggested in The AWK Programming Language by Aho,
Kernighan and Weinberger. That solution divides the problem into three
steps:

1. 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 to the end of the phrase. So the output of
this phase for the first line of our input above 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.

3. Unrotate and print the permuted index, which involves finding the
separator, putting the phrase back together and printing it properly
formatted.

Which seems like a great explanation, and in depth, but it's just not clicking for me. First off, I don't really understand what a permutated index is, even after some extensive Googling. The second thing that I'm confused on is the steps they give for that algorithm. In step 1 it says to create some rotations of the output, but then in step 3 (after sorting them) it says to unrotate them and write it. Wouldn't this just write that sentence however many words there are in it times. Like, for example, the following sentence:
"This is a test sentence."

Would just be written 5 times? Because you get x rotations, where x is the number of words in the sentence. Then you unrotate and write it all out..

Obviously I'm missing something, but figured that maybe explaining my thinking could help get a better explanation. It all boils down to figuring out exactly what a permutated index is, which seems more difficult than it should be.
Thanks for any help.

[MrHutch]

Here's what I can make of this. Please note, that I'm in no way an expert on permuted indices.

So, the first output, the one with eight lines. The way I see it, is it's using the words in each phrase as an index and printing them by which phrase they appear in alphabetically.

The quick brown fox      // brown
jumped over the fence    // fence
The quick brown fox      // fox
jumped over the fence    // jumped
jumped over the fence    // over
The quick brown fox      // quick
jumped over the fence    // the f 
The quick brown fox      // The q 

With regards to the sort algorithm, I think the example is a bit poor by only giving you the one phrase. I doesn't really seem to show the effect. If you do it with both phrases, it works a little better.

Step 1 - Rotations

The quick brown fox
quick brown fox The
brown fox The quick
fox The quick brown
jumped over the fence
over the fence jumped
the fence jumped over
fence jumped over the

Step 2 - Sort

// Sorting strings alphabetically gives
brown fox The quick
fence jumped over the
fox The quick brown
jumped over the fence
over the fence jumped
quick brown fox The
the fence jumped over
The quick brown fox

Step 3 - Rotate string back to original order

The quick brown fox
jumped over the fence
The quick brown fox
jumped over the fence
jumped over the fence
The quick brown fox
jumped over the fence
The quick brown fox

And there's your permuted index.

Hope this helps.

[o3hC5Di1]

Hi there,

The first example they give is not really clear to me, I'm not seeing the permutational side of that at all.

I'm really bad at Mathematics, but I thought permutations were the amount of different orders a given sequence could appear in. For instance, with 1,2,3:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

It seems to like what they want you to do is to read every line of input, then put every seperate word (string) seperately in an array, i.e.:

std::string words[4];
std::string input = "The Quick Brown Fox"
// =>
words[3] = "Brown";

That would allow you to loop and permutate the indexes of the word-array (so you'd be working with numbers rather than text).

Sorry I can't be of more specific help, perhaps one of the experts around here would be so kind to give you his or her thoughts on this - I would be interested to read them as well.

All the best,
NwN

[MrHutch]

NwN, in math terms you're correct, those are permutations.

However, in this example they're dealing with a permuted index for phrases like they said in the first post:

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

So their output is indexed (alphabetically ordered) by those eight words (see the first code example in my post above). The permutations occur at step 1 of their algorithm, though not like a mathematical permutation where every possible combination would be listed.

[o3hC5Di1]

Hi there,

Thanks for clearing that up iHutch105, I was typing my post as you posted yours, so I hadn't read it yet.

I didn't realise "permuted index" is a programming concept either, so thanks for clearing that up too. :)

All the best,
NwN