Author |
Topic: To find all synonymous sentences (Read 1799 times) |
|
blackJack
Junior Member
2b \/ ~2b
Gender: 
Posts: 55
|
 |
To find all synonymous sentences
« on: Apr 5th, 2010, 5:05am » |
 Quote  Modify
|
A dictionary kind of mapping is given to you for some words, for example : 'AB' -> 'CS' , 'A' -> 'FGH','F'->'H' etc.
Now given a sentence (suppose group of characters) print all poosible synonymous sentences.
Suppose sentence given is 'AABCS', so output should be:
AABCS
FGHABCS
AFGHBCS
ACSCS
FGHFGHBCS
FGHCSCS
Lets not consider the translation of synonymous words... like 'F' can be again converted to 'H', but that is not needed as of now for simplicity.
|
| « Last Edit: Apr 5th, 2010, 5:24am by blackJack » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: To find all synonymous sentences
« Reply #1 on: Apr 5th, 2010, 7:29am » |
Quote Modify
|
As long as one sequence of characters can't be translated in two ways, the following should work. (And otherwise you just need a way to cycle through all translations)
Python Code:d = {'AB':'CS' , 'A':'FGH','F':'H'};
s = "AABCS"
def foo(pre, str):
..if len(str) == 0:
....print pre;
..else:
....foo(pre+str[0], str[1:]);
....for i in range(0, len(str)+1):
......if str[0:i] in d:
........foo(pre+d[str[0:i]], str[i:]);
foo("", s) |
|
This isn't necessarily the best way to do it though. For one thing I look at every sub-string to see if it can be translated as a whole. It's be more efficient to build a transducer. I think that'd be O(n) in the output size.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print