Combinaison de regroupement en Python / Ruby / PHP / Golang (Go)

Réalisez des combinaisons de regroupement en Python / Ruby / PHP / Golang (Go) en utilisant des nombres Sterling

Ici réalise le calcul de base du nombre de combinaisons, et ici , Réalise des combinaisons superposées avec une limite supérieure. En eux, c'était un modèle d'extraction d'un groupe et de création d'un autre. Le procédé de changement d'un certain groupe à une pluralité de groupes, c'est-à-dire le calcul du nombre de motifs de combinaison pour le regroupement, peut être réalisé en utilisant le nombre de livres sterling.

Référence: [Numéro Sterling](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)

Numéro sterling de type 2

• Pour faciliter l'explication, à partir du nombre de livres sterling de type 2 ... Calculez le nombre de motifs qui divisent un groupe composé de n en k groupes. Par exemple, lors de la division du groupe (A, B, C, D) en deux, le nombre de motifs tels que ((A, B), (C, D)) et ((A, B, C), (D)) est utilisé. calculer. Cependant, ((A, B), (C, D)) et ((C, D), (A, B)) sont considérés comme identiques et traités comme 1 compte. En outre, l'ordre dans les groupes divisés tels que ((A, B), (C, D)) et ((B, A), (D, C)) n'est pas pris en compte.

\begin{eqnarray}
S(n,k)
 =
  \begin{cases}
    0 & ( k=0 \hspace{4pt}Et\hspace{4pt} n \neq k ) \\
    1 & ( n=k \hspace{4pt}Ou\hspace{4pt} k=1 ) \\
    S(n−1,k−1)+kS(n−1,k) & ( a \lt b )
  \end{cases}
\end{eqnarray}

Numéro sterling de type 1

Les différences par rapport au nombre de livres sterling de type 2 sont comptées séparément, à l'exception de celles qui peuvent être remplacées par une patrouille dans des groupes distincts. En d'autres termes, dans le cas de la division du groupe (A, B, C, D) en deux, ((A), (B, C, D)) et ((A), (B, D, C)) sont traités différemment. Mais ((A), (B, C, D)) et ((A), (D, C, B)), ((A), (B, D, C)) et ((A), ( Les motifs tels que C, D, B)) sont traités de la même manière.

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

Code source

Python3

• En fait, comme je n'ai jamais utilisé le nombre sterling de type 1, la valeur par défaut est de type 2 en Python3.

def stirling(n, k, s=True):
    """
n est le nombre d'éléments dans le groupe, k est le nombre de groupes à diviser et s est le deuxième type.(default)qu'il s'agisse
    """
    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))

Résultat de sortie

31
274

Ruby2.4 La valeur par défaut est le deuxième 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)

Résultat de sortie

31
274

PHP7.1 La valeur par défaut est le deuxième 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);

Résultat de sortie

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

Résultat de sortie

31
274