Recursion

Ruby
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 :slight_smile: 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)

2

(‘aaa’…‘zzz’).to_a

Cheers,

Erik.

3

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

4

Instead of

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

Use

addChar( str + c, level + 1 )

=)

5

On 25/11/05, cyberco [email protected] 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([[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/

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, :slight_smile:
Berco

7

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 :slight_smile:

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 :slight_smile: Any suggestions?

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

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

“cyberco” [email protected] writes:

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 :slight_smile: Any suggestions?

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

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. :slight_smile: