algorithm practice: combinations

gistfile1.rb

require 'pp'

def succ(a, n)
  # a is an array of integers <= n
  # see tests
  return nil if n == 0
  a = Array.new(a)
  x = a.pop
  if x + 1 < n
    return a + [x + 1]
  else
    return nil if a.empty?
    first = succ(a, x)
    return nil if first.nil?
    return first + [first[-1] + 1]
  end
end

def assert_succ(a, n, b)
  unless succ(a, n) == b
    pp [a, n, b]
    pp succ(a,n)
    raise 'foo'
  end
end

assert_succ([], 0, nil)
assert_succ([0], 1, nil)
assert_succ([1], 2, nil)
assert_succ([0], 2, [1])
assert_succ([0, 1], 2, nil)
assert_succ([0, 1], 3, [0, 2])
assert_succ([0, 2], 3, [1, 2])
assert_succ([0, 3], 4, [1, 2])
assert_succ([1, 2], 3, nil)
assert_succ([1, 2], 4, [1,3])
assert_succ([1, 3], 4, [2,3])
assert_succ([2, 3], 4, nil)
assert_succ([0, 2, 3], 4, [1,2,3])
# puts "\n\nSUCCESS\n\n"

x = ['a', 'b', 'c', 'd', 'e', 'f']

def combine(a, n)
  iso = Array.new(n) { |i| i }
  while iso do
    yield iso.map { |i| a[i] }
    iso = succ(iso, a.size)
  end
end

combine(x, 3) do |a|
  pp a*''
end