wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> To find all synonymous sentences
        
(Message started by: blackJack on Apr 5^th, 2010, 5:05am)

Title: To find all synonymous sentences
Post by blackJack on Apr 5^th, 2010, 5:05am

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.

Title: Re: To find all synonymous sentences
Post by towr on Apr 5^th, 2010, 7:29am

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 (http://en.wikipedia.org/wiki/Finite-state_machine#Transducers). I think that'd be O(n) in the output size.