recursion

[cyberco]

I'm trying to print every combination of three characters from the
range (a..z). I thought recursion would be the most elegant solution,
but that got me quite confused :) Any suggestions? Here's my
(erronous) attempt:

________________________

def addChar(str, level)
('a'..'z').each {|c|
if level == 2
puts str + c
else
str += c
addChar(str, level + 1)
end
}
end

addChar("", 0)

[Erik Terpstra]

('aaa'..'zzz').to_a

Cheers,

Erik.

[Erik Terpstra]

Or 'a'..'zzz' if you want every combination 'up to' 3 characters.

[Nathan Smith]

Instead of

> str += c
> addChar(str, level + 1)

Use

addChar( str + c, level + 1 )

=)

[Brian Schröder]

Thoug 'aaa'..'zzz' is certainly the most elegeant, maybe it would help
if you'd try to understand this recursion

def combinations(elements, length)
return [] if length == 0
return elements if length == 1
result = []
elements.each do | element |
combinations(elements, length - 1).each do | combination |
result << element + combination
end
end
result
end

# What you want
puts combinations(('a'..'c').to_a, 3)

# Using the power of ducktyping
combinations([[1], [2], [3]], 3).each do | combination |
p combination
end

# What does this calculate?
combinations((1..3).to_a, 3).each do | combination |
p combination
end

cheers,

Brian

--
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/

[mathew]

cyberco wrote:
> I'm trying to print every combination of three characters from the
> range (a..z). I thought recursion would be the most elegant solution,
> but that got me quite confused :) Any suggestions?

Definitely not recursion. Consider that your problem is equivalent to
printing every possible 3 digit number in base 26 :-)

Not that you can't do it recursively:

def f(lhs)
if lhs.length == 3
puts lhs
else
for c in 'a'..'z'
f(lhs + c)
end
end
end

f('')

mathew
--
<URL:http://www.pobox.com/~meta/>
My parents went to the lost kingdom of Hyrule
and all I got was this lousy triforce.

[cyberco]

Thanks! That is certaily a elegant solution, but I wonder what the
logic behind it is. I can't find any documentation on this usage of
ranges, any pointers?

Groeten, :)
Berco

[cyberco]

The recursive solution I found is:
__________________________
def addChar(str, level)
if level == 2

('a'..'z').each {|c|

p str + c
@file << str + c + ' '
}
else

('a'..'z').each {|c|

addChar(str + c, level + 1)
}
end
end
__________________________

I'm merely posting it here for future reference. Erik's solution
('aaa'..'zzz').to_a is ofcourse much more usable and elegant :)

[George Ogata]

"cyberco" <cyb...@gmail.com> writes:

Here's how you get there:

('aaa'..'zzz').to_a is clearly a call to Range#to_a.

* `ri Range` tells you that Range gets #to_a from Enumerable.
* `ri Enumerable#to_a` tells you that it returns the elements yielded by
a call to #each. (Oh wait, it doesn't. It should... . Really,
it's no secret that all of Enumerable's methods are defined in terms
of #each, but I can't find it anywhere in the rdoc comments.)
* `ri Range#each` tells you that the elements yielded come from
successive calls to each element's #succ method, starting with the
start object ('aaa' in this case).
* `ri String#succ` tells you that 'aaa'.succ will return 'aab' (and so
on).
* Profit! (Er... QED.)

HTH,
George.

[Gavin Kistner]

On Nov 25, 2005, at 3:52 PM, mathew wrote:
> cyberco wrote:
>> I'm trying to print every combination of three characters from the
>> range (a..z). I thought recursion would be the most elegant solution,
>> but that got me quite confused :) Any suggestions?
>
> Definitely not recursion. Consider that your problem is equivalent
> to printing every possible 3 digit number in base 26 :-)

Which leads to this alternative solution:

( 'aaa'.to_i(36)..'zzz'.to_i(36) ).map{ |i| (str=i.to_s(36)) =~ /^[a-
z]{3}$/ && str }.compact

Far less elegant than 'aaa'..'zzz', but there you have it. :)