Author |
Topic: Find chronological order of characters (Read 2193 times) |
|
sateesp
Newbie
Gender: 
Posts: 35
|
 |
Find chronological order of characters
« on: Jul 29th, 2010, 7:15am » |
 Quote  Modify
|
Given set words from language X in dictionary order and these words are sufficient to arrange the language ‘X’ characters in chronological order. Give the algorithm for finding/constructing the chronological order?
Example: Suppose given words from language X: { cb,cy,b} and output is (c,b,y) ( this the chronological order of ‘X’ language character set)
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Find chronological order of characters
« Reply #1 on: Jul 29th, 2010, 7:24am » |
Quote Modify
|
I don't understand the question. Where does time come in? (i.e. what's chronological about it.) And why is the set of words in the example not actually in dictionary (alphabetic) order?
Do you want the order of first occurrence of the characters in the concatenation of an array of words?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Find chronological order of characters
« Reply #2 on: Jul 29th, 2010, 7:35am » |
Quote Modify
|
I guess the quesion is as follows: suppose a new alphabet has been designed. You are given an array that is in dictionary order according to that new alphabet, and you are asked to derive what the alphabet is.
|
|
IP Logged |
|
|
|
sateesp
Newbie
Gender:
Posts: 35
|
|
Re: Find chronological order of characters
« Reply #3 on: Jul 29th, 2010, 8:58am » |
Quote Modify
|
@Tower, When I mean chronological order, I am asking about alphabet order. (Sorry I have used wrong word (chronological) here).
@pex, your understanding is right.
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Find chronological order of characters
« Reply #4 on: Jul 29th, 2010, 11:18am » |
Quote Modify
|
on Jul 29th, 2010, 7:15am, sateesp wrote:Given set words from language X in dictionary order and these words are sufficient to arrange the language ‘X’ characters in chronological order. Give the algorithm for finding/constructing the chronological order?
Example: Suppose given words from language X: { cb,cy,b} and output is (c,b,y) ( this the chronological order of ‘X’ language character set)
|
|
you can do something like this:
1. first compare the ith symbol of the words and form equations like { c < b }
(examining the 1st symbol of the words which is c,c,b , we can say c < b)
2. then for all the words with ith symbol same, repeat the 1st step for i+1.
3. Start with i = 1;
for example
at i = 1 { c < b }
i = 2 { b < y }
combine all the equations and solve ( fairly easy ).
and for efficiently executing 3 steps, you can use a Trie.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
sateesp
Newbie
Gender:
Posts: 35
|
|
Re: Find chronological order of characters
« Reply #5 on: Aug 21st, 2010, 2:14am » |
Quote Modify
|
Following is my solution to this question:
1. Find alphabet from the given set of words (it’s not required to be actual alphabet order)
Input_alphabet[], count = number of unique alphabets
2. Construct the Matrix of size count*count and fill with all zeros.
int order[count][count]; //
if order[i][j] == 0 means haven’t found the relation between input_alphabet[i] & input_alphabet[j]
if order[i][j] ==1 means input_alphabet[i] < input_alphabet[j]
3. Take any two strings in the input array. Compare these two strings and you will find the relation between two characters. Example: if you get the relation like {c<b}, represent the relation in the matrix by placing ‘1’ in that location.
4. With above matrix information, you can form a directed acyclic graph.
Find the node which has in-degree zero. Remove that node from the graph and update the graph. Repeat this process until you extract all the nodes.
Example:
Suppose given words { dzc, cc,cza,az,aa}
| | D | C | Z | A | | D | 0 | 1 | 0 | 1 | | C | 0 | 0 | 1 | 1 | | Z | 0 | 0 | 0 | 1 | | A | 0 | 0 | 0 | 0 |
From that matrix, you can find the in-degree zero vertices and start deleting.
Delete D (it has zero in-degree)
Delete C
Delete Z
Delete A.
Alphabetical order is: D,C,Z,A
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Find chronological order of characters
« Reply #6 on: Aug 23rd, 2010, 2:53am » |
Quote Modify
|
I suppose you used assumption all characters are sorted individually.
In czech/slovak the 'ch' double character single syllabe is wrongly interpreted as compound single char. Unfortunately there is nobody able to correct this rule.
So the following order of slowak words is correct dictionary order:
cesta
dal
hodina
choroba
meno
viachodnotovy
viacmenej
In the first case ch was one syllabe, in the other it was two syllabes in the componed word based on viac and hodnotovej.
So the stated problem in some languages is more complex than one would expected.
|
|
IP Logged |
|
|
|
sateesp
Newbie
Gender:
Posts: 35
|
|
Re: Find chronological order of characters
« Reply #7 on: Aug 23rd, 2010, 9:25am » |
Quote Modify
|
Got it 
Btw, is my algo correct if we assume all alphabets are single character symbol?
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Find chronological order of characters
« Reply #8 on: Aug 24th, 2010, 4:53am » |
Quote Modify
|
Yes each pair of consecutive words defines relation (directed edge) between first characters at which they differ. You are asked to find topological order of the characters (vertices).
When the dictionary is huge compared to the alphabet size and it usually is, edges would be defined several times so some "hash" table would help. The table you have used works well (with identitiy as a hash function).
For the topological sort part, I would use DFS.
|
| « Last Edit: Aug 24th, 2010, 4:53am by Hippo » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print