Wednesday, February 13, 2008

Ruby: All Combinations / Permutations up to length n-1 of a String

What?
In writing a Scrabble like game, I needed a quick fix to get all possible combinations of a string (of length 1..n). I would then look these combinations up in the dictionary to determine if they are words valid for placement.

Why?
It would be nice to able to do the following:

'abc'.combinations.each do |combo|
dictionary.lookup(combo)
end
So I hacked up the following:
class String
# Get all the combinations of a string.
# Returns an array of all combinations of a string
# If a block is given, then that block is called once for each combination
def combinations &action
ret = []
0.upto length-1 do |n|
#rest = self.split('') # regular
rest = self.split(//u) # UTF-8
picked = rest.delete_at n
action.call picked if action
ret << picked
rest.join.combinations.each do |perm|
genperm = picked+perm
ret << genperm
action.call genperm if action
end
end
ret
end
end
Which does the following:
p 'abc'.combinations # => ["a", "ab", "abc", "ac", "acb", "b", "ba", "bac", "bc", "bca", "c", "ca", "cab", "cb", "cba"]

'abc'.combinations do |combination|
puts combination
end
# =>
# a
# ab
# abc
# ac
# acb
# b
# ba
# bac
# bc
# bca
# c
# ca
# cab
# cb
# cba
Just what I wanted!


1 comment:

Kale Co Jakim said...


Hi, Great.. Tutorial is just awesome..It is really helpful for a newbie like me.. I am a regular follower of your blog. Really very informative post you shared here. Kindly keep blogging. If anyone wants to become a Front end developer learn from Javascript Training in Chennai . or learn thru Javascript Training in Chennai.