String vector sorting

Question

I havent used sorting and alogorithms much and am Ok with vectors. Recently i faced an interesting question and want your suggestions with how to solve it. So, below is my question.

Q, I have been given 4 character strings in a vector and have to arrange those in a particular order depending on what those characters are. So, that the last character of any string should match with the first character of any other string and the last character of this string should be matched with the first character of any other string and this way i have to create a longest possible string.

For eg if i have a string vector like "ABCD" "TGHI" "DADC" "IYUR" "CXYT" so it would be arrange like "ABCD"then there would be the third string"DADC" then there would be the fifth string"CXYT" and so on So, the result will be "ABCD""DADC""CXYT""TGHI""IYUR".

Now,i was wondering if it would be a good idea to check each string with other string if it is 'compatible' according to the above rules.. so if i have 5 strings in the vector then i would have 5+4+3+2+1 possiblties and if for eg i have 20 strings then it would increase alot, so is this a good idea or is there any other good efficient solution to this... Thanks alot and hope (most of) you understand.

Please do not say "for eg", ever. Only the alot may say that. — Kerrek SB
– Kerrek SB, Commented Feb 9, 2012 at 19:37
"Sorting" isn't the right term, because you don't have a linear order on your elements. This is something more complicated. — Kerrek SB
– Kerrek SB, Commented Feb 9, 2012 at 19:40
Looks like "Longest path problem", which unfortunately is NP-complete. — zch
– zch, Commented Feb 9, 2012 at 19:51

RussS · Accepted Answer · 2012-02-09 19:42:08Z

1

Imagine every letter as a node in a graph. Each word represents a directed pathway between two letters in. "ACCA" defines A->A "BAAC" B-->C . Within this graph you would like to find a Eulerian Path. http://en.wikipedia.org/wiki/Eulerian_path . The Eulerian Path is defined as a path that visits every edge exactly once and since each edge represents a word that means you have used all the words!

answered Feb 9, 2012 at 19:42

RussS

16.6k1 gold badge36 silver badges62 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Sufian Latif · Accepted Answer · 2012-02-09 19:37:50Z

0

A better approach may be to build a directed graph using the strings. There will be an edge from string s1 to string s2 if the last character of s1 is the same as the first character of s2. Then you can try to find the longest path in the graph.

answered Feb 9, 2012 at 19:37

Sufian Latif

13.4k3 gold badges36 silver badges71 bronze badges

Collectives™ on Stack Overflow

String vector sorting

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related