CODEWITHSUNDEEP
c++stringsorting
0aps
0aps

Reputation: 93

Sorting criteria for ordering this words?

I want to do two types of sorting, the first one is as follow:

Given a set of distinct lines with two words separate with a space, order them in a way that the next line has a first word equal to the last word of the previous line. For example:

Should give something like:

I read every line as a string, put it inside a vector and used a sort comparison function like this:

bool cmp(std::string a, std::string b)
{
    std::string prb = a.substr(a.find(" ")+1),
                prb2 = b.substr(0, b.find(" "));

    return prb == prb2;
}

But to get the desire result I have to sort twice. I don't understand why exactly that happens.

The second ordering criteria is:

Given a set of words order then so that the next word has the same first letter as the last letter of the previous word. For example:

Should give something like:

I did something like this, but doesn't seems to work properly. 

bool cmp(std::string a, std::string b)
{
    if(b[b.size()-1] == a[0] && a[0] != b[0]) return false;
    return b[b.size()-1] == a[0];
}

How can I make this two sorting works fine?

Upvotes: 0

Views: 116

Answers (2)

Igor Tandetnik
Igor Tandetnik

Reputation: 52471

First, problem #2 can be reduced to problem #1. Replace each string with a string consisting of the first letter and the last letter, separated by space; e.g. AEIOU becomes A U. Then it's clear that solving problem #1 on these new strings will also give the solution to problem #2 on original strings.

Second, this is a problem of finding a Hamiltonian path in a directed graph. The graph in question consists of the input strings as vertices, with an edge drawn between every pair of vertices of the form X Y and Y Z.

The problem, as stated, is underspecified: it's not clear what is considered the right answer when the graph doesn't contain a Hamiltonian path. Your example has Pamela Luisa followed by Pedro Luis, which doesn't satisfy the requirement. One possible interpretation is that of finding a minimum path cover.

Upvotes: 2

genisage
genisage

Reputation: 1169

There is probably a better approach than this, but I would start by going through all of the words and assigning them numbers 0 to n.
Then each line can be represented as an ordered pair of numbers.
Then if there are k lines, create a (k x k) matrix of bools.
In each spot put true if the second word in the pair for that column matches the first word in the pair for that row, and false otherwise.
At that point you should be able to implement a simple backtracking search to find some sequence of lines (x_0, x_1,...) such that matrix[x_i][x_{i+1}] = true for all i.
Hope that helps.
If you can solve the first problem, the second should be very similar.

Upvotes: 0

Related Questions