From: Michael Ulm <michael.ulm@...>
Date: 2005-11-15T19:01:02+09:00
Subject: Re: Recursive functions

William James wrote:

> hans.sjunnesson@gmail.com wrote:
> 
>>I know that this is a trivial problem, but I'm having a hard time
>>solving it with tuby. I could use a little extra help with my
>>programming in ruby skills.
>>
>>The problem I'm faced to solving (taken from a puzzle in a newspaper)
>>is a series of alphabetical triplets like:
>>
>>ubc
>>deg
>>lap
>>pyq
>>
>>ved
>>run
>>pac
>>ken
>>alm
>>mli
>>rnt
>>alg
>>
>>Combining a letter from each triplet, you can form words which will
>>form a sentence (in the above case: 'ugly duckling').
>>What I want to do is go through all possible permutations of
>>characters, in the triplets, and crossreference them with a dictionary
>>to create all possible permutations of words in a sentence. I've put
>>the above triplets into an array of arrays: [["ubc", "deg", "lap",
>>"pyq"], ["ved", "run", "pac", "ken", "alm", "mli", "rnt", "alg"]]. Now
>>here's my problem. How do I recurse the words in the best way? What I
>>want to do is start to check "udlp", "udly", "udlq", then "udap",
>>"uday", "udaq" and so on?
> 
> 
> There are 3**4 combinations. Instead of using recursion, we can simply
> count from 0 to 3**4-1:
> 
> dict={}; IO.readlines(ARGV.pop||"words.txt").each{|w| dict[w.chomp]=""}
> triplets = [ %w(ubc deg lap pyq), %w(ved run pac ken alm mli rnt alg) ]
> 
> def num_to_str( n, base, ary )
>   n.to_s(base).rjust(ary.size,"0").split('').zip( ary ).
>   inject(""){|out,x| out << x.first.tr("012",x.last) }

to keep the function usable for any base up to 36, change
that line to

   inject(""){|out,x| out << x.first.tr("0-9a-z",x.last) }

> end
> 
> triplets.each do |ary|   (3**ary.size).times{|i|
>   word=(num_to_str(i,3,ary)); p word if dict[word]}
> end
> 

Michael


-- 
Michael Ulm
R&D Team
ISIS Information Systems Austria
tel: +43 2236 27551-219, fax: +43 2236 21081
e-mail: michael.ulm@isis-papyrus.com
Visit our Website: www.isis-papyrus.com