 # Recursion

#1

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:

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

#2

(‘aaa’…‘zzz’).to_a

Cheers,

Erik.

#3

Or ‘a’…‘zzz’ if you want every combination ‘up to’ 3 characters.

#4

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

Use

addChar( str + c, level + 1 )

=)

#5

On 25/11/05, cyberco removed_email_address@domain.invalid wrote:

``````        puts str + c
``````

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([, , ], 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

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

#6

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

#7

The recursive solution I found is:

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 #8

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

#9

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?

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.

#10

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. 