Python/Ruby/PHP/Golangで上限のある重複組み合わせのパターン数を算出する
3種類の果物から12個取り出す場合の数は、それぞれの果物が12個以上ある場合、重複組み合わせの方法で、算出することができる。
しかし、それぞれの果物が6個という上限がある場合、この方法では算出できない。
そのため、上限がある重複組み合わせについては、別の方法で実現する必要がある。
この例では、さいころを3回振り、出た目の総和が12になる場合の数と等価であるので、この数式は意外と流用できる（と思う）。
控除原理
このような上限のある重複組み合わせは控除原理に基づいて算出する方法がある。
参考サイトはこちら。
※「控除原理」を「個数定理」という名称でも呼ばれているが、「個数定理」は正式な名称なのだろうか・・・数学関連の書籍をあたってみよう。
数式
参考サイトから、上限をm、果物の種類をn（振ったさいころの数）、総和をtとすると下記の式で算出できる。
\begin{eqnarray}
\sum_{ k = 0 }^{ [ \frac{ t - n }{ m } ]} (-1)^k \cdot {}_n \mathrm{ C }_k \cdot {}_n \mathrm{ H }_{ t - n - m \cdot k }
\end{eqnarray}
m = 6、n = 3、t = 12のとき25となる。
ソースコード
Python3
import functools as ft
def permutation(n, k):
if k > n:
return 0
elif 0 < k <= n:
return ft.reduce(lambda x, y:x * y, [n - v for v in range(k)])
else:
return 1
def factorial(n):
return permutation(n, n - 1)
def combination(n, k):
return int(permutation(n, k) / factorial(k))
def homogeneous(n, k):
return combination(n + k - 1, k)
def homogeneous_with_limit(m, n, t):
return sum([(-1)**k * combination(n, k) * homogeneous(n, t - n - m * k) \
for k in range(0, int((t - n) / m) + 1)])
if __name__ == '__main__':
print(homogeneous_with_limit(6, 3, 12))
出力結果
25
Ruby2.4
def permutation(n, k)
if k > n
0
elsif 0 < k && k <= n then ((n - k + 1)..n).inject(:*)
else 1
end
end
def factorial(n)
permutation(n, n - 1)
end
def combination(n, k)
(permutation(n, k) / factorial(k)).to_i
end
def homogeneous(n, k)
combination(n + k - 1, k)
end
def homogeneous_with_limit(m, n, t)
(0..((t - n) / m)).inject(0) {|s, k| s + (-1)**k * combination(n, k) * homogeneous(n, t - n - m * k)}
end
p homogeneous_with_limit(6, 3, 12)
出力結果
25
PHP7.1
<?php
function permutation(int $n, int $k) : int {
if ($k > $n) return 0;
elseif (0 < $k && $k <= $n)
return array_reduce(range($n - $k + 1, $n), function ($c, $v) { return $c *= $v; }, 1);
else return 1;
}
function factorial(int $n) : int {
return permutation($n, $n - 1);
}
function combination(int $n, int $k) : int {
return intval(permutation($n, $k) / factorial($k));
}
function homogeneous(int $n, int $k) : int {
return combination($n + $k - 1, $k);
}
function homogeneous_with_limit(int $m, int $n, int $t) : int {
return array_reduce(range(0, intval(($t - $n) / $m)), function ($s, $k) use ($m, $n, $t) {
return $s += (-1) ** $k * combination($n, $k) * homogeneous($n, $t - $n - $m * $k);
});
}
print(homogeneous_with_limit(6, 3, 12));
出力結果
25
Golang
package main;
import (
"fmt"
"math"
)
func permutation(n int, k int) int {
v := 1
if 0 < k && k <= n {
for i := 0; i < k; i++ {
v *= (n - i)
}
} else if k > n {
v = 0
}
return v
}
func factorial(n int) int {
return permutation(n, n - 1)
}
func combination(n int, k int) int {
return permutation(n, k) / factorial(k)
}
func homogeneous(n int, k int) int {
return combination(n + k - 1, k)
}
func homogeneous_with_limit(m int, n int, t int) int {
e := int((t - n) / m) + 1
v := 0
for i := 0; i < e; i++ {
v += int(math.Pow(-1, float64(i))) * combination(n, i) * homogeneous(n, t - n - m *i)
}
return v
}
func main () {
fmt.Printf("%v\n", homogeneous_with_limit(6, 3, 12))
}
出力結果
25
その他
控除原理はエラトステネスの篩の証明でも利用している。またガウス記号（[x]）が懐かしい。
課題が多々あって、たとえば、さいころ3個振って、出た目が(3,5,4)と(3,4,5)でも12となるが、このような順序を考慮しない場合、別のアプローチをとる必要がある。
また、3個のさいころの目の最大値が6ではなく、それぞれ別の値となる場合も、他のアプローチで対応する必要がある。
順序を考慮しないケースについては、どこかでアルゴリズムの課題として主題されていたが、数式化できず、ひたすらループを回す羽目となったので、もう一度挑戦したい。
最大値が異なるケースは、漸化式をどこかで発見して、それっきり。