Forum: Ruby recursion

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
cyberco (Guest)
on 2005-11-25 17:43
(Received via mailing list)
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 (Guest)
on 2005-11-25 17:55
(Received via mailing list)
('aaa'..'zzz').to_a

Cheers,

Erik.
erik (Guest)
on 2005-11-25 17:59
(Received via mailing list)
Or 'a'..'zzz' if you want every combination 'up to' 3 characters.
nathan.smith (Guest)
on 2005-11-25 17:59
(Received via mailing list)
Instead of

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

Use

addChar( str + c, level + 1 )


=)
ruby.brian (Guest)
on 2005-11-25 18:07
(Received via mailing list)
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([[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/
meta (Guest)
on 2005-11-26 00:55
(Received via mailing list)
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
cyberco (Guest)
on 2005-11-27 14:45
(Received via mailing list)
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 (Guest)
on 2005-11-27 14:45
(Received via mailing list)
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 :)
g_ogata (Guest)
on 2005-11-27 15:54
(Received via mailing list)
"cyberco" <removed_email_address@domain.invalid> 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.
gavin (Guest)
on 2005-11-27 22:22
(Received via mailing list)
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. :)
This topic is locked and can not be replied to.