Here realizes the basic calculation of the number of combinations, and here , Achieves overlapping combinations with an upper limit. In them, it was a pattern of extracting from one group and creating another. A method of changing from a certain group to a plurality of groups, that is, calculating the number of combination patterns for grouping can be realized by using the Stirling number.
Reference: [Stirling number](https://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%BF%E3%83%BC%E3%83%AA%E3%83%B3% E3% 82% B0% E6% 95% B0)
\begin{eqnarray}
S(n,k)
=
\begin{cases}
0 & ( k=0 \hspace{4pt}And\hspace{4pt} n \neq k ) \\
1 & ( n=k \hspace{4pt}Or\hspace{4pt} k=1 ) \\
S(n−1,k−1)+kS(n−1,k) & ( a \lt b )
\end{cases}
\end{eqnarray}
Differences from the Type 2 Stirling number are counted separately, except for those that can be cyclically replaced in separate groups. In other words, in the case of dividing the group (A, B, C, D) into two, ((A), (B, C, D)) and ((A), (B, D, C)) are treated differently. But ((A), (B, C, D)) and ((A), (D, C, B)), ((A), (B, D, C)) and ((A), ( Patterns such as C, D, B)) are treated the same.
\begin{eqnarray}
S(n,k)
=
\begin{cases}
0 & ( k=0 \hspace{4pt}And\hspace{4pt} n \neq k ) \\
1 & ( n=k ) \\
S(n−1,k−1)+(n-1)S(n−1,k) & ( a \lt b )
\end{cases}
\end{eqnarray}
Python3
def stirling(n, k, s=True):
"""
n is the number of elements in the group, k is the number of groups to divide, and s is the second type.(default)whether
"""
return (0 if n < k else
1 if n == k else
0 if k == 0 else
stirling(n - 1, k - 1, s) + (k if s else n - 1) * stirling(n - 1, k, s)
)
if __name__ == '__main__':
print(stirling(6, 2))
print(stirling(6, 2, False))
Output result
31
274
Ruby2.4 The default is the second type.
def stirling(n, k, s=true)
if n < k
0
elsif n == k then 1
elsif n == 0 then 0
else
stirling(n - 1, k - 1, s) + (s ? k : n - 1) * stirling(n - 1, k, s)
end
end
p stirling(6, 2)
p stirling(6, 2, false)
Output result
31
274
PHP7.1 The default is the second type.
<?php
function stirling(int $n, int $k, bool $s = true) : int {
if ($n < $k) return 0;
elseif ($n == $k) return 1;
elseif ($n == 0) return 0;
else return stirling($n - 1, $k - 1, $s) + ($s ? $k : $n - 1) * stirling($n - 1, $k, $s);
}
print(stirling(6, 2). PHP_EOL);
print(stirling(6, 2, false). PHP_EOL);
Output result
31
274
Golang
package main;
import "fmt"
func stirling(n int, k int, s bool) int {
switch {
case n < k:
return 0
case n == k:
return 1
case k == 0:
return 0
case s:
return stirling(n - 1, k - 1, s) + k * stirling(n - 1, k, s)
default:
return stirling(n - 1, k - 1, s) + (n - 1) * stirling(n - 1, k, s)
}
}
func main() {
fmt.Printf("%v\n", stirling(6, 2, true))
fmt.Printf("%v\n", stirling(6, 2, false))
}
Output result
31
274
Recommended Posts