combination.rb

# coding: utf-8
# 2017-02-04
# kinds種類の物がそれぞれlimit個あった時に
# その中からn個取ったときの組み合わせの数を求める関数

# 例えば麻雀の萬子は1～9種類の物がそれぞれ4枚あり
# その中から8枚取ったときの組み合わせの数は
# f(8,9,4) = 11385

# 参考：上限のある重複組合わせ(?)
# https://oshiete.goo.ne.jp/qa/5281101.html


def f(n,kinds,limit)
  if (n == 0) then return 1 end
  if (n <= 0) then return 0 end
  if (kinds == 1) then
    if (n == 1 || n <= limit) then
      return 1;
    else
      return 0;
    end
  end
  result = 0;
  limit.downto(0) {|lim|
    result += f(n-lim,kinds-1,limit);
  }
  return result;
end