Python/Ruby/PHP/Golang(Go)でグループ分けの組み合わせ

スターリング数を使ってPython/Ruby/PHP/Golang(Go)でグループ分けの組み合わせを実現する

こちらで、基本的な組み合わせ数の算出を実現し、こちらでは、上限のある重複組み合わせを実現。それらでは、あるグループから抽出して別の1つのグループを作成するパターンであった。
あるグループから複数のグループにする、つまりグループ分けの組み合わせパターン数を算出する方法はスターリング数を利用して実現できる。

参考：スターリング数

第2種スターリング数

*説明の都合上、第2種スターリング数から・・・
n個で構成されているグループをk個のグループに分けるパターン数を算出する。例えば、グループ(A, B, C, D)を2つに分ける場合、((A, B), (C, D))や((A, B, C), (D))といったパターン数を算出する。ただし、((A, B), (C, D))と((C, D), (A, B))は同一と見なし1カウント扱い。また、((A, B), (C, D))と((B, A), (D, C))のように分割されたグループ内での順序は考慮しない。

\begin{eqnarray}
S(n,k)
 =
  \begin{cases}
    0 & ( k=0 \hspace{4pt} かつ \hspace{4pt} n \neq k ) \\
    1 & ( n=k \hspace{4pt} または \hspace{4pt} k=1 ) \\
    S(n−1,k−1)+kS(n−1,k) & ( a \lt b )
  \end{cases}
\end{eqnarray}

第1種スターリング数

第2種スターリング数と異なるのは分けたグループで巡回置換できるものを除き、別カウントされる。つまり、グループ(A, B, C, D)を2つに分けるケースでは、((A), (B, C, D))と((A), (B, D, C))は別扱いだが、((A), (B, C, D))と((A), (D, C, B))、((A), (B, D, C))と((A), (C, D, B))といったパターンは同一扱いとされる。

\begin{eqnarray}
S(n,k)
 =
  \begin{cases}
    0 & ( k=0 \hspace{4pt} かつ \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

※実際のところ、第1種スターリング数を使ったことがないためPython3ではデフォルトを第2種とした。

def stirling(n, k, s=True):
    """
    ｎはグループの要素数、kは分割するグループ数、sは第2種(default)かどうか
    """
    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))

出力結果

31
274

Ruby2.4

デフォルトを第2種とした。

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)

出力結果

31
274

PHP7.1

デフォルトを第2種とした。

<?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);

出力結果

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

出力結果

31
274