gistfile1.rb

def multi_choose(choices, size, index = 0, hax = Hash.new)
  return [] if index == choices.size
  hax[[size, index]] ||= begin
    base = [choices[index]] * size
    s = base
    multisets = [base]
    0.upto(size - 1) do |i|
      s = s.dup
      s.pop
      multi_choose(choices, i + 1, index + 1, hax).each {|s2| multisets << s + s2}
    end
    multisets
  end
end