# Combinadics In Ruby

Join the DZone community and get the full member experience.

Join For Free```
Provides Array combination iterator, generator, combinadics, and Integer binomial coefficient calculation (a.k.a. "choose function"). Apparently those are enough buzzwords that you found it, congrats ;)
Documentation in the code comments. References on wikipedia:
http://en.wikipedia.org/wiki/Combination
http://en.wikipedia.org/wiki/Combinadic
http://en.wikipedia.org/wiki/Binomial_coefficient
``````
# == Usage
# This is an include for combinadics that monkey patches the Array and Integer classes.
# On Array it provides an each_choose block iterator for each of the self.size.choose(k) combinations.
# If passed a block, this will pass each combination to the block, otherwise an array with all combinations is returned.
# On Array it also provides a choose_index method to find the i-th combination of self.each_choose(k)
# On Integer it provides a binomial coefficient calculator. e.g. 20.choose(3)
#
# == Author
# Caleb Harrelson - what.a.hoopy.frood@gmail.com
#
# == Copyright
# Copyright (c) 2009 Caleb Harrelson. Licensed under the MIT License:
# http://www.opensource.org/licenses/mit-license.php
require 'rdoc/usage'
class Array
# when called without a block, returns an array with each combination.
# when called with a block, yields each combination to the block.
def each_choose(k, &block)
raise ArgumentError, "The combination size (#{k}) must be <= the array size (#{size}).", caller if k > size
raise ArgumentError, "The combination size (#{k}) cannot be negative.", caller if k < 0
if block == nil
results = []
size.choose(k).times { |i| results << choose_index(k, i) }
return results
end
size.choose(k).times { |i| yield choose_index(k, i) }
end
# returns the combination at index i of self.each_choose(k)
def choose_index(n, i)
results = []
size.times do |x|
break if n == 0
threshold = (size - x - 1).choose(n - 1)
if i < threshold
results << self[x]
n -= 1
else
i = i - threshold
end
end
return results
end
end
class Integer
# calculates binomial coefficient of self choose k
# not recommended for large numbers as binomial coefficients get large quickly... e.g. 100 choose 50 is 100891344545564193334812497256
def choose(k)
return 0 if (k > self)
n = self
r = 1
1.upto(k) do |d|
r *= n
r /= d
n -= 1
end
return r
end
end
if __FILE__ == $0
arr = [:apple, :bear, :candle, :dog, :envelope, :frankfurt, :goodness, :heart, :indigo]
puts "Iterate over choose 3 from #{arr.inspect}"
arr.each_choose(3) {|c| puts c.inspect}
puts ""
arr = arr.slice(0..3)
puts "Return array of choose 2 from #{arr.inspect}"
puts arr.each_choose(2).inspect
end
```

Opinions expressed by DZone contributors are their own.

Comments