Algorithmensammlung: Kombinatorik: Binomialkoeffizient

Algorithmensammlung: Kombinatorik

• Binomialkoeffizient

Fakultät

Der Artikel beschreibt die für die Kombinatorik wichtige  Fakultätsfunktion. Direkt verwendet wird sie, um die Anzahl der Möglichkeiten zu berechnen, alle n Kugeln aus einer Urne ohne Zurücklegen unter Beachtung der Reihenfolge anzuordnen. Ferner spielt sie u. a. bei der Definition des Binomialkoeffizienten eine wichtige Rolle.

Basic C64

F!  = 1*2*3*4*5* ......*F

Die Fakultät einer natürlichen Zahl wird berechnet.

 10 INPUT F
 12 S = 1
 20 FOR N = 1 TO F
 30 S = S*N
 50 NEXT 
 60 PRINT "die Fakultaet von ";F;" = ";S

Die ganze Reihe aller Fakultäten von 1 bis 100 wird berechnet.

 F = 1
 For k = 1 To 100
 F = F * k
 Print "Die Fakultät von "; k; " = ", F
 Next k

Java

Die folgende Java-Methode zur Berechnung der Fakultät verwendet die Klasse BigInteger, die sich mit der Zeile

import java.math.BigInteger;

am Anfang des Programms einbinden lässt.

public static BigInteger factorial (int n) {

  if (n < 0) {
    System.out.println("Argument negativ!");
    return null;
    }

  BigInteger f = BigInteger.ONE;
  for (int i=2; i<=n; i++)
    f = f.multiply(BigInteger.valueOf(i));
  return f;

  }

Python

Die Funktion bekommt eine Ganzzahl größer 0 als Parameter übergeben und gibt den Wert der Fakultätsfunktion zurück.

# Getestet unter Python 3.4, sollte aber unter allen 3.x-Versionen laufen
def fakultaet(n):
    f = 1
    for i in range(1, n + 1):
        f = f * i
    return f

Ab Python2.6 gibt es dafür die Funktion math.factorial.

Für sehr große n kann die Fakultät näherungsweise mit der  Stirling-Formel berechnet werden.

FreePascal

Der Vollständigkeit halber sei die rekursive Implementation gezeigt:

{**
	recursively calculates factorial of given n
	
	\param n the factorial to calculate of
	\returns factorial of n
*}
function factorial(const n: longword): qword;
begin
	// optimization: then-branch is executed most of the time
	if n > 1 then
	begin
		factorial := factorial(n - 1) * n;
	end
	else
	begin
		factorial := 1;
	end;
end;

Interessanter ist die iterative Implementation. Hier eine, die sowohl x86-64-assembler und Pascal kombiniert:

{**
	iteratively calculates factorial of n
	
	\param n the upper limit
	\return the factorial of n,
	unless the result is out of range of the function's domain
}
function factorial(const n: longint): qword;
{$ifdef CPUx86_64}
assembler;
{$goto on}
label
	factorial_iterate, factorial_done;
{$asmMode intel}
asm
	// ecx is used by loop instruction as counter variable
	mov ecx, n // ecx := n
	// rax is where we calculate our product
	mov rax, 1 // rax := 1
	
	test rcx, rcx // commonBits := rcx
	// don't enter loop, since ecx = 0 it loops over all integers
	jz factorial_done // if commonBits = 0 then goto done
	
	// load r13 with failure value, bc cmov can't process immediates
	xor r13, r13 // r13 := 0
	
factorial_iterate:
	mul rcx // rdx:rax := rax * rcx
	
	test rdx, rdx // commonBits := rdx and rdx
	// commonBits only has a positive magnitude if rdx is non-zero
	// continue looping while rdx remains zero
	loopz factorial_iterate // dec(ecx)
	// if ecx <> 0 and ZF = 0 then goto iterate
	
	// void result, if we need the "high" register
	cmovnz rax, r13 // if not ZF then rax := 0
	
factorial_done:
	// the @result macro represents the function's return value
	mov @result, rax // result := rax
end;
{$else}
var
	/// temporary iterator variable
	i: longint;
	/// space to calculate the product in
	product: qword;
begin
	product := 1;
	
	// note: for-loop limits are in Pascal inclusive
	// limit two, because multiplying by one is neutral
	for i := n downto 2 do
	begin
		product := product * n;
	end;
	
	factorial := product;
end;
{$endif}

Binomialkoeffizient (Kombination ohne Zurücklegen)

Der Artikel beschreibt die Algorithmen zu den Artikeln  Binomialkoeffizient und  Abzählende Kombinatorik.

Der folgende Algorithmus berechnet den Binomialkoeffizienten, der in der abzählenden Kombinatorik die Anzahl verschiedener Ergebnisse berechnet, wenn in einer Ziehung die gezogenen Elemente nicht zurückgelegt wurden, aber die Reihenfolge bei der Ziehung keine Bedeutung hat. Dies liefert beispielsweise beim Lotto 6 aus 49 die Anzahl der verschiedenen Möglichkeiten, ein Zahlenfeld auf dem Tippschein auszufüllen.

Pseudocode

n und k seien natürliche Zahlen oder gleich 0. Außerdem gelte 0 ≤ k ≤ n.

function binomialkoeffizient (n, k)
  if k > n - k then k ← n - k
  b ← 1
  for i ← 1 to k do
    b ← b * (n + 1 - i) / i
  return b

Java

Wie bei der Fakultät muss am Anfang des Programms mit

import java.math.BigInteger;

die Klasse BigInteger eingebunden werden.

public static BigInteger binomialCoefficient (int n, int k) {
  if (n < 0 || k < 0) {
    System.out.println("Argument negativ!");
    return null;
    }
  if (k > n) return BigInteger.ZERO;
  k = Math.min(k,n-k);
  BigInteger bc = BigInteger.ONE;
  for (int i=1; i<=k; i++) {
    bc = bc.multiply(BigInteger.valueOf(n+1-i));
    bc = bc.divide(BigInteger.valueOf(i));
    }
  return bc;
  }

Python

Im folgenden Quelltext wurde die normalerweise im Mathematikunterricht vermittelte Definition des Binomialkoeffizienten unter Verwendung der Implementierung der Fakultät von oben implementiert. Die Parameter müssen ganzzahlig sein.

# Getestet unter Python 3.4, sollte aber unter allen 3.x-Versionen laufen
def binomialkoeffizient(n, k):
    return fakultaet(n) // (fakultaet(k)*fakultaet(n-k))  # integer-Division, da Binominalkoeffizienten bekanntlich ganze Zahlen sind

Der folgende Algorithmus ist um einiges effizienter.

# Getestet unter Python 3.4, sollte aber unter allen 3.x-Versionen laufen
def binomialkoeffizient(n, k):
    if k == 0: return 1
    if 2*k > n:
        ergebnis = binomialkoeffizient(n, n-k)
    else:
        ergebnis = n-k+1
        for i in range(2, k+1):  # 2 <= i <= k
            ergebnis *= (n-k+i)  # Selbstmultiplikation
            ergebnis //= i 
    return ergebnis

# (ergebnis * (n-k+i)) / i ist bei jedem Schritt ganzzahlig,
# daher kann Integer-Division verwendet werden;
# die Größe von int ist in Python nur durch den Speicherplatz begrenzt.

Visual Basic for Applications

Der Algorithmus hat folgende Merkmale:

• Im Laufe der Berechnung wird kein Zwischenergebnis größer als das Endergebnis, so dass ein Überlauf nur dann eintritt, wenn auch das Endergebnis einen Überlauf auslösen würde
• Divisionen werden meist so ausgeführt, dass das Ergebnis ganzzahlig bleibt.

Grundsätzlich lässt sich der Bereich der Ergebnisse mit voller Genauigkeit erweitern, wenn als Rückgabewert der Funktion der VBA-Datentyp Currency (größter ganzzahlig darstellbarer Wert 922.337.203.685.477) statt Long (größter ganzzahlig darstellbarer Wert 2.147.483.647) verwendet wird. Speziell bei der Verwendung als Excel-Tabellenfunktion muss dann das Zahlenformat manuell vorgegeben werden, da sonst automatisch die Zelle das Zahlenformat Währung erhält. Die Datentypen der Argumente n und k können nicht geändert werden, da die Mod-Funktion mit Argumenten vom Datentyp Long (oder kleiner) arbeitet.

Public Function BinomialKoeffizient(n As Long, ByVal k As Long) As Long
    Dim i As Long, s As Long
    
    ' Vergrößerung der Geschwindigkeit
    If n < k + k Then k = n - k
    
    ' Startwerte setzen
    s = n - k + 1
    BinomialKoeffizient = 1
        
    For i = 1 To k
        If s Mod i = 0 Then ' Teilbarkeit prüfen
            BinomialKoeffizient = BinomialKoeffizient * (s / i)
        Else
            BinomialKoeffizient = (BinomialKoeffizient / i) * s
        End If
        s = s + 1
    Next

End Function

Wenn n und k Dezimalzahlen sind, werden sie bei der Übergabe an die Funktion auf ganzzahlige Werte gerundet (impliziter  typecast durch  VBA), dabei wird nach IEEE-754 ( mathematische Rundung) gerundet. Dadurch führt beispielsweise die Übergabe von k = 0,5 zur Abrundung auf k = 0.

Die Funktion enthält keine Fehlerbehandlung, da die erforderlichen Programmzeilen und Rückgabewerte programmspezifisch für Excel, Access und andere Office-Programme anzupassen wären. Verwendung als Funktion in Visual Basic:

Ergebnis = BinomialKoeffizient(49, 6)

Anwendung als Excel-Tabellenfunktion:

=BinomialKoeffizient(49;6)

Das Ergebnis ist in beiden Fällen 13 983 816; Excel bietet auch die Tabellenfunktion Kombinationen() an, die gelegentlich ungenaue Ergebnisse liefert, beispielsweise ein Rundungsartefakt für =BinomialKoeffizient(40;17)

Tipps

Bitte ausbauen

Mit Python 3.4 wurde erstmals ein Statistik-Modul, statistics, ausgeliefert, das gängige statistische Methoden wie Mittelwert- und Streumaßberechnung anbietet.

Weblinks

• Rosettacode
  • Factorial
  • Evaluate binomial coefficients
  • Combinations and permutations