Grouping combination in Python / Ruby / PHP / Golang (Go)

Achieve grouping combinations in Python / Ruby / PHP / Golang (Go) using Stirling numbers

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)

Type 2 Stirling number

• For convenience of explanation, from the number of Type 2 Stirling numbers ... Calculate the number of patterns that divide a group consisting of n into k groups. For example, when dividing the group (A, B, C, D) into two, the number of patterns such as ((A, B), (C, D)) and ((A, B, C), (D)) is used. calculate. However, ((A, B), (C, D)) and ((C, D), (A, B)) are regarded as the same and treated as 1 count. Also, the order within the divided groups such as ((A, B), (C, D)) and ((B, A), (D, C)) is not considered.

\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}

Type 1 Stirling number

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}

Source code

Python3

• Actually, since I have never used the first Stirling number, the default is set to the second in 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