Skip to content

Instantly share code, notes, and snippets.

@arya
Created March 27, 2009 04:38
Show Gist options
  • Save arya/86537 to your computer and use it in GitHub Desktop.
Save arya/86537 to your computer and use it in GitHub Desktop.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment