recursion

C

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)
 
N

Nathan Smith

--Apple-Mail-1-8172659
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
charset=US-ASCII;
format=flowed

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

Use

addChar( str + c, level + 1 )


=)


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)


--Apple-Mail-1-8172659--
 
B

Brian Schröder

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 =3D=3D 2
puts str + c
else
str +=3D c
addChar(str, level + 1)
end
}
end

addChar("", 0)


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 =3D=3D 0
return elements if length =3D=3D 1
result =3D []
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
 
C

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
 
C

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 :)
 
G

George Ogata

cyberco said:
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.
 
G

Gavin Kistner

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

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top