Berechnen und Erzeugen von Faktoren, Permutationen und Kombinationen in Python

Geschäft

Das Standardmodul math für mathematische Funktionen in Python kann zur Berechnung von Faktorzahlen verwendet werden. SciPy verfügt auch über Funktionen zur Berechnung der Gesamtzahl von Permutationen und Kombinationen.

Das Modul itertools kann auch verwendet werden, um Permutationen und Kombinationen aus Listen (Arrays) usw. zu erzeugen und sie aufzuzählen.

Das Folgende wird hier erklärt, zusammen mit einem Beispielcode.

  • faktoriell:math.factorial()
  • Berechnen Sie die Gesamtzahl der Permutationen
    • math.factorial()
    • scipy.special.perm()
  • Erzeugen und Aufzählen von Permutationen aus einer Liste:itertools.permutations()
  • Berechnen Sie die Gesamtzahl der Kombinationen
    • math.factorial()
    • scipy.special.comb()
    • Wie man math.factorial() nicht verwendet
  • Erzeugen und Aufzählen von Kombinationen aus Listen:itertools.combinations()
  • Berechnen Sie die Gesamtzahl der doppelten Kombinationen
  • Erzeugen und Aufzählen von doppelten Kombinationen aus einer Liste:itertools.combinations_with_replacement()

Als Beispiel für die Verwendung von Permutationen wird auch das Folgende erläutert.

  • Anagramme aus Zeichenketten erstellen

Wenn Sie eine Kombination von Elementen aus mehreren Auflistungen anstelle einer einzigen Auflistung erstellen möchten, verwenden Sie itertools.product() im itertools-Modul.

faktoriell: math.factorial()

Das Mathematikmodul bietet eine Funktion factorial(), die die Fakultät zurückgibt.

import math

print(math.factorial(5))
# 120

print(math.factorial(0))
# 1

Nicht-ganzzahlige, negative Werte führen zu einem ValueError.

# print(math.factorial(1.5))
# ValueError: factorial() only accepts integral values

# print(math.factorial(-1))
# ValueError: factorial() not defined for negative values

Berechnen Sie die Gesamtzahl der Permutationen

math.factorial()

Permutationen sind die Anzahl der Fälle, in denen r aus n verschiedenen ausgewählt und in eine Reihe gestellt werden.

Die Gesamtzahl der Permutationen, p, wird durch die folgende Gleichung unter Verwendung von Faktorzahlen ermittelt.

p = n! / (n - r)!

Sie kann wie folgt mit der Funktion math.factorial() berechnet werden, die die Fakultät zurückgibt. Der ⌘-Operator, der eine ganzzahlige Division durchführt, wird verwendet, um einen ganzzahligen Typ zurückzugeben.

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

print(permutations_count(4, 2))
# 12

print(permutations_count(4, 4))
# 24

scipy.special.perm()

SciPy bietet eine Funktion scipy.special.perm(), die die Gesamtzahl der Permutationen zurückgibt. Eine separate SciPy-Installation ist erforderlich. Verfügbar ab Version 0.14.0.

from scipy.special import perm

print(perm(4, 2))
# 12.0

print(perm(4, 2, exact=True))
# 12

print(perm(4, 4, exact=True))
# 24

exact=False
Das dritte Argument ist standardmäßig wie oben eingestellt und gibt eine Fließkommazahl zurück. Wenn Sie es als Ganzzahl erhalten möchten, müssen Sie es wie folgt einstellen.
exact=True

Beachten Sie, dass nur “import scipy” das scipy.special-Modul nicht lädt.

Führen Sie perm() als “from scipy.special import perm” wie im obigen Beispiel aus, oder führen Sie scipy.special.perm() als “import scipy.special” aus.

Erzeugen und Aufzählen von Permutationen aus einer Liste: itertools.permutations()

Nicht nur Gesamtzahlen, sondern auch Permutationen können aus Listen (Arrays) usw. erzeugt und aufgezählt werden.

Verwenden Sie die Funktion permutations() des Moduls itertools.

Die Übergabe einer Iterablen (vom Typ Liste oder Menge) als erstes Argument und der Anzahl der auszuwählenden Stücke als zweites Argument gibt einen Iterator für diese Permutation zurück.

import itertools

l = ['a', 'b', 'c', 'd']

p = itertools.permutations(l, 2)

print(type(p))
# <class 'itertools.permutations'>

Um sie alle aufzuzählen, können Sie eine for-Schleife verwenden.

for v in itertools.permutations(l, 2):
    print(v)
# ('a', 'b')
# ('a', 'c')
# ('a', 'd')
# ('b', 'a')
# ('b', 'c')
# ('b', 'd')
# ('c', 'a')
# ('c', 'b')
# ('c', 'd')
# ('d', 'a')
# ('d', 'b')
# ('d', 'c')

Da es sich um einen endlichen Iterator handelt, kann er auch mit list() in einen Listentyp umgewandelt werden.

Wenn die Anzahl der Elemente in der Liste mit len() ermittelt wird, kann bestätigt werden, dass sie mit der Gesamtzahl der aus der Fakultät berechneten Permutationen übereinstimmt.

p_list = list(itertools.permutations(l, 2))

print(p_list)
# [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'a'), ('b', 'c'), ('b', 'd'), ('c', 'a'), ('c', 'b'), ('c', 'd'), ('d', 'a'), ('d', 'b'), ('d', 'c')]

print(len(p_list))
# 12

Wird das zweite Argument weggelassen, wird die Permutation zur Auswahl aller Elemente zurückgegeben.

for v in itertools.permutations(l):
    print(v)
# ('a', 'b', 'c', 'd')
# ('a', 'b', 'd', 'c')
# ('a', 'c', 'b', 'd')
# ('a', 'c', 'd', 'b')
# ('a', 'd', 'b', 'c')
# ('a', 'd', 'c', 'b')
# ('b', 'a', 'c', 'd')
# ('b', 'a', 'd', 'c')
# ('b', 'c', 'a', 'd')
# ('b', 'c', 'd', 'a')
# ('b', 'd', 'a', 'c')
# ('b', 'd', 'c', 'a')
# ('c', 'a', 'b', 'd')
# ('c', 'a', 'd', 'b')
# ('c', 'b', 'a', 'd')
# ('c', 'b', 'd', 'a')
# ('c', 'd', 'a', 'b')
# ('c', 'd', 'b', 'a')
# ('d', 'a', 'b', 'c')
# ('d', 'a', 'c', 'b')
# ('d', 'b', 'a', 'c')
# ('d', 'b', 'c', 'a')
# ('d', 'c', 'a', 'b')
# ('d', 'c', 'b', 'a')

print(len(list(itertools.permutations(l))))
# 24

In itertools.permutations() werden die Elemente nach ihrer Position und nicht nach ihrem Wert behandelt. Doppelte Werte werden nicht berücksichtigt.

l = ['a', 'a']

for v in itertools.permutations(l, 2):
    print(v)
# ('a', 'a')
# ('a', 'a')

Das Gleiche gilt für die folgenden Funktionen, die im Folgenden beschrieben werden.

  • itertools.combinations()
  • itertools.combinations_with_replacement()

Berechnen Sie die Gesamtzahl der Kombinationen

math.factorial()

Die Anzahl der Kombinationen ist die Anzahl von r Stücken, die aus n verschiedenen Stücken ausgewählt werden können. Die Reihenfolge wird wie bei Permutationen nicht berücksichtigt.

Die Gesamtzahl der Kombinationen c ergibt sich aus der folgenden Gleichung.

c = n! / (r! * (n - r)!)

Sie kann wie folgt mit der Funktion math.factorial() berechnet werden, die die Fakultät zurückgibt. Der ⌘-Operator, der eine ganzzahlige Division durchführt, wird verwendet, um einen ganzzahligen Typ zurückzugeben.

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

print(combinations_count(4, 2))
# 6

scipy.special.comb()

SciPy bietet eine Funktion scipy.special.comb(), die die Gesamtzahl der Permutationen zurückgibt. Eine separate SciPy-Installation ist erforderlich. Verfügbar ab Version 0.14.0. Beachten Sie, dass scipy.misc.comb() die unten beschriebene Wiederholung von Argumenten nicht implementiert.

from scipy.special import comb

print(comb(4, 2))
# 6.0

print(comb(4, 2, exact=True))
# 6

print(comb(4, 0, exact=True))
# 1

exact=False
Wie bei scipy.special.perm() ist das dritte Argument standardmäßig wie oben eingestellt und gibt eine Fließkommazahl zurück. Beachten Sie, dass Sie es wie folgt setzen müssen, wenn Sie es als Ganzzahl erhalten möchten.
exact=True
Die Gesamtzahl der doppelten Kombinationen kann auch mit dem vierten Argument, Wiederholung, ermittelt werden. Dies wird im Folgenden beschrieben.

Auch hier ist zu beachten, dass nur “import scipy” das scipy.special-Modul nicht lädt.

Wie im obigen Beispiel führen Sie comb() als “from scipy.special import comb” aus oder führen Sie scipy.special.comb() als “import scipy.special” aus. Das gleiche gilt für “scipy.misc”.

Wie man math.factorial() nicht verwendet

Eine andere Methode, die nur die Standardbibliothek verwendet und schneller ist als die Methode mit math.factorial(), ist die folgende Methode.

from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

print(combinations_count(4, 2))
# 6

print(combinations_count(4, 0))
# 1

Erzeugen und Aufzählen von Kombinationen aus Listen: itertools.combinations()

Es ist möglich, alle Kombinationen aus Listen (Arrays) usw. sowie Gesamtzahlen zu erzeugen und aufzuzählen.

Verwenden Sie die Funktion combinations() des Moduls itertools.

Die Übergabe einer Iterablen (vom Typ Liste oder Menge) als erstes Argument und der Anzahl der auszuwählenden Stücke als zweites Argument gibt den Iterator für diese Kombination zurück.

l = ['a', 'b', 'c', 'd']

c = itertools.combinations(l, 2)

print(type(c))
# <class 'itertools.combinations'>

for v in itertools.combinations(l, 2):
    print(v)
# ('a', 'b')
# ('a', 'c')
# ('a', 'd')
# ('b', 'c')
# ('b', 'd')
# ('c', 'd')

c_list = list(itertools.combinations(l, 2))

print(c_list)
# [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]

print(len(c_list))
# 6

Berechnen Sie die Gesamtzahl der doppelten Kombinationen

Die Anzahl der doppelten Kombinationen ist die Anzahl der Fälle, in denen r aus n verschiedenen Kombinationen ausgewählt werden, wobei Duplikate berücksichtigt werden.

Die Gesamtzahl der doppelten Kombinationen ist gleich der Anzahl der Kombinationen, die (r) aus (n + r – 1) verschiedenen Kombinationen zu wählen sind.

Daher können wir die oben definierte Funktion verwenden, um die Gesamtzahl der Kombinationen zu berechnen.

def combinations_with_replacement_count(n, r):
    return combinations_count(n + r - 1, r)

print(combinations_with_replacement_count(4, 2))
# 10

In der oben beschriebenen “scipy.special.comb()” kann die Gesamtzahl der doppelten Kombinationen durch Setzen des vierten Arguments “repetition=True” ermittelt werden.
Beachten Sie, dass das Argument “repetition” in “scipy.misc.comb()” in Versionen vor “SciPy0.14.0” nicht implementiert ist.

from scipy.special import comb

print(comb(4, 2, exact=True, repetition=True))
# 10

Erzeugen und Aufzählen von doppelten Kombinationen aus einer Liste: itertools.combinations_with_replacement()

Es ist möglich, alle doppelten Kombinationen aus Listen (Arrays) usw. sowie Gesamtzahlen zu erzeugen und aufzuzählen.

Verwenden Sie die Funktion combinations_with_replacement() im itertools-Modul.

Die Übergabe einer Iterablen (vom Typ Liste oder Menge) als erstes Argument und der Anzahl der auszuwählenden Teile als zweites Argument gibt einen Iterator für diese überlappende Kombination zurück.

h = itertools.combinations_with_replacement(l, 2)

print(type(h))
# <class 'itertools.combinations_with_replacement'>

for v in itertools.combinations_with_replacement(l, 2):
    print(v)
# ('a', 'a')
# ('a', 'b')
# ('a', 'c')
# ('a', 'd')
# ('b', 'b')
# ('b', 'c')
# ('b', 'd')
# ('c', 'c')
# ('c', 'd')
# ('d', 'd')

h_list = list(itertools.combinations_with_replacement(l, 2))

print(h_list)
# [('a', 'a'), ('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'b'), ('b', 'c'), ('b', 'd'), ('c', 'c'), ('c', 'd'), ('d', 'd')]

print(len(h_list))
# 10

Anagramme aus Zeichenketten erstellen

Mit Itertools.permutations() lassen sich auf einfache Weise Permutationen (Anagramme) von Zeichenketten erstellen.

s = 'arc'

for v in itertools.permutations(s):
    print(v)
# ('a', 'r', 'c')
# ('a', 'c', 'r')
# ('r', 'a', 'c')
# ('r', 'c', 'a')
# ('c', 'a', 'r')
# ('c', 'r', 'a')

Um ein Tupel aus jeweils einem Zeichen zu einer Zeichenkette zu kombinieren und daraus eine Liste zu machen, gehen Sie wie folgt vor

anagram_list = [''.join(v) for v in itertools.permutations(s)]

print(anagram_list)
# ['arc', 'acr', 'rac', 'rca', 'car', 'cra']

Die join()-Methode, die Elemente einer Liste oder eines Tupels zu einer Zeichenkette verkettet, und die Notation für das Listenverständnis werden verwendet.

Copied title and URL