Gruppierungskombination in Python / Ruby / PHP / Golang (Go)

Erzielen Sie Gruppierungskombinationen in Python / Ruby / PHP / Golang (Go) mit Sterling-Zahlen

Hier realisiert die grundlegende Berechnung der Anzahl der Kombinationen und hier Erzielt überlappende Kombinationen mit einer Obergrenze. In ihnen war es ein Muster, aus einer Gruppe zu extrahieren und eine andere zu erschaffen. Ein Verfahren zum Wechseln von einer bestimmten Gruppe zu einer Vielzahl von Gruppen, dh zum Berechnen der Anzahl von Kombinationsmustern für die Gruppierung, kann unter Verwendung der Anzahl von Pfund Sterling realisiert werden.

Referenz: [Sterling-Nummer](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)

Typ 2 Sterling Nummer

• Zur Vereinfachung der Erklärung aus der Anzahl der Typ 2 Sterling ... Berechnen Sie die Anzahl der Muster, die eine aus n bestehende Gruppe in k Gruppen unterteilen. Wenn beispielsweise die Gruppe (A, B, C, D) in zwei Teile geteilt wird, wird die Anzahl der Muster wie ((A, B), (C, D)) und ((A, B, C), (D)) verwendet. Berechnung. ((A, B), (C, D)) und ((C, D), (A, B)) werden jedoch als gleich angesehen und als 1 Zählung behandelt. Auch die Reihenfolge innerhalb der geteilten Gruppen wie ((A, B), (C, D)) und ((B, A), (D, C)) wird nicht berücksichtigt.

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

Typ 1 Sterling Nummer

Unterschiede zur Sterling-Zahl vom Typ 2 werden separat gezählt, mit Ausnahme derjenigen, die zyklisch in separaten Gruppen ersetzt werden können. Mit anderen Worten, im Fall der Aufteilung der Gruppe (A, B, C, D) in zwei werden ((A), (B, C, D)) und ((A), (B, D, C)) unterschiedlich behandelt. Aber ((A), (B, C, D)) und ((A), (D, C, B)), ((A), (B, D, C)) und ((A), Muster wie C, D, B)) werden gleich behandelt.

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

Quellcode

Python3

• Da ich die Sterling-Nummer vom Typ 1 noch nie verwendet habe, ist die Standardeinstellung in Python3 auf Typ 2 eingestellt.

def stirling(n, k, s=True):
    """
n ist die Anzahl der Elemente in der Gruppe, k ist die Anzahl der zu teilenden Gruppen und s ist der zweite Typ.(default)ob
    """
    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))

Ausgabeergebnis

31
274

Ruby2.4 Der Standardwert ist der zweite Typ.

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)

Ausgabeergebnis

31
274

PHP7.1 Der Standardwert ist der zweite Typ.

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

Ausgabeergebnis

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

Ausgabeergebnis

31
274