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

\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

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

Grouping combination in Python / Ruby / PHP / Golang (Go)
Handle prime numbers in Python / Ruby / PHP / Golang (Go)
Overlapping combinations with limits in Python / Ruby / PHP / Golang (Go)
Factorial, permutations, (duplicate) combinations in Python / Ruby / PHP / Golang (Go)
Realize PHP / Python generator with Golang / Ruby
[Scraping Summary] | Python Node.js PHP Ruby Go VBA | Scraping Yahoo! Top in 6 languages
GNU GLOBAL (gtags) + α in Go, Ruby, Python
Differences in string processing between Python, Ruby, JS, PHP (combination and variable expansion)
How to handle JSON in Ruby, Python, JavaScript, PHP
About Perl, Python, PHP, Ruby
Hello World in various languages [Python / PHP / Java / Perl / Ruby]
Multi-stage selection (Go / C # / Ruby / Python)
Dynamic proxy with python, ruby, PHP
Avoid nested loops in PHP and Python
Differences between Ruby and Python in scope
Big difference in ruby, python, httpd performance
PHP / Python / Ruby sample hitting Path API
Obtaining temporary AWS credentials in PHP, Python
Referencing INI files in Python or Ruby
[Basic grammar] Differences between Ruby / Python / PHP
Let's make a combination calculation in Python
Try something like Python for-else in Ruby
How to write Ruby to_s in Python
Implemented memoization recursion and exploration in Python and Go
I tried using mecab with python2.7, ruby2.3, php7
Y / n processing in bash, python and Go
POST JSON in Python and receive it in PHP
Regular expression symbolic group name in Python / Ruby
Quadtree in Python --2
Python in optimization
CURL in python
Metaprogramming in Python
Python 3.3 in Anaconda
Geocoding in python
SendKeys in Python
Meta-analysis in Python
Unittest in python
Python with Go
Epoch in Python
Discord in Python
Sudoku in Python
DCI in Python
quicksort in python
nCr in python
Plink in Python
Constant in python
Lifegame in Python.
FizzBuzz in Python
Rock-paper-scissors in Ruby
Sqlite in python
StepAIC in Python
This Week's Algorithm: Shortest Path Calculation! (Permutation iterator in Ruby / Python / C # / VB / Go)
N-gram in python
LINE-Bot [0] in Python
Disassemble in Python
Reflection in Python
Constant in python
format in python
Scons in Python3
Puyo Puyo in python
python in virtualenv