Finden Sie die Reihenfolge / Kombination in Python

Einführung

Als ich das Programm sah, das die Reihenfolge und Kombinationen auflistet, die ich vor langer Zeit erstellt habe, konnte ich nicht sofort verstehen, wie ich es erstellt habe, und habe versucht, es als Überprüfung neu zu erstellen. Ich werde einen Artikel schreiben, damit ich ihn nicht vergesse.

Das Programm in diesem Artikel ist es jedoch nicht wert, da es mit itertools leicht zu finden ist. Darüber hinaus enthält die offizielle Python-Dokumentation ein übersichtliches und schönes Programm, das nach Sequenzen und Kombinationen fragt. Es ist nur ein persönliches Lernprotokoll.

Erstellt mit Python 3.6.1.

Jedes soll wie folgt geschrieben werden.

• Gegebene Daten (Liste oder Tupel): Daten --Datenlänge: n --Nummer zur Auswahl: r
• Gesamtzahl der duplizierten Sequenzen: H (n, r)
• Gesamtzahl der Spalten: P (n, r)
• Gesamtzahl der doppelten Kombinationen: Π (n, r)
• Gesamtzahl der Kombinationen: C (n, r)

itertools

Was Sie finden werden, können Sie mit itertools finden.

--Doppelte Bestellung: list(itertools.product(data, repeat=r)) --Auftrag: list(itertools.permutations(data, r))

• Doppelte Kombination: list(itertools.combinations_with_replacement(data, r)) --Kombination: list(itertools.combinations(data, r))

Entscheidend

Betrachten Sie der Einfachheit halber zunächst nur den Fall, drei aus den angegebenen Daten zu extrahieren (r = 3).

Doppelte Bestellung

Die Reihenfolge mit Duplikaten ist

1. Sie können herausnehmen, was Sie einmal herausgenommen haben, und es wieder herausnehmen
2. Die Reihenfolge der Extraktion ist sinnvoll (auch wenn die Elemente, aus denen sich die Menge zusammensetzt, gleich sind und wenn die Reihenfolge unterschiedlich ist, werden sie als unterschiedlich behandelt).

Das ist. Ein Paar finden

1. Extrahieren Sie eine aus den Daten
2. Setzen Sie das, was Sie in 1 herausgenommen haben, zurück und nehmen Sie eines wieder heraus.
3. Setzen Sie das, was Sie in Schritt 2 herausgenommen haben, zurück und nehmen Sie eines wieder heraus.

Der aufgerufene Prozess wird ausgeführt. Um nach allen Paaren zu fragen

1. Schleife für das erste Element
2. Eine Schleife, die ein zweites Element sucht, das in der ersten Schleife verschachtelt ist
3. Schleife, um das dritte Element zu finden, das in der zweiten Schleife verschachtelt ist

Verengen Sie die Schleife so. Wenn Sie versuchen, sofort ein Programm zu erstellen, sieht es wie folgt aus.

result = []
for i in data:
  for j in data:
    for k in data:
      result.append([i, j, k])

Mit Listeneinschlussnotation

result = [[i, j, k] for i in data for j in data for k in data]

Die Listeneinschlussnotation wird jedoch nicht für die wesentliche Verarbeitung verwendet. Auch wenn es etwas überflüssig ist, später darüber nachzudenken, werde ich nach dem Index fragen und dann den Dateninhalt wie folgt abrufen.

result = []
for i in range(len(data)):
  for j in range(len(data)):
    for k in range(len(data)):
      result.append([data[i], data[j], data[k]])

Permutation

Die Reihenfolge ist

1. Ich kann nicht herausnehmen, was ich einmal herausgenommen habe
2. Die Reihenfolge der Extraktion ist sinnvoll (auch wenn die Elemente, aus denen sich die Menge zusammensetzt, gleich sind und wenn die Reihenfolge unterschiedlich ist, werden sie als unterschiedlich behandelt).

Das ist. Mit anderen Worten, es kann durch Hinzufügen eines Prozesses erhalten werden, der es unmöglich macht, das, was einmal herausgenommen wurde, mit Duplikaten in den Prozess der Bestellung abzurufen. Daher ist der Prozess zum Finden eines Satzes wie folgt.

1. Extrahieren Sie eine aus den Daten
2. Nehmen Sie einen aus dem Rest heraus, außer dem, der in 1 herausgenommen wurde.
3. Nehmen Sie einen aus dem Rest heraus, außer dem, der in 1-2 herausgenommen wurde.

Der Rest der Struktur kann auf die gleiche Weise wie eine sequentielle Sequenz mit Duplikaten erreicht werden. Alternativ können Sie dies anfordern, indem Sie die Duplikate aus der duplizierten Bestellung entfernen. Ich werde diese Methode jedoch nicht in Betracht ziehen, da es viele verschwendete Wiederholungen gibt.

Das Programm sieht folgendermaßen aus: Hier definieren und verwenden wir die Funktion listExcludedIndices, die eine Liste mit Ausnahme derjenigen zurückgibt, die einmal abgerufen wurde.

def listExcludedIndices(data, indices=[]):
  return [x for i, x in enumerate(data) if i not in indices]

result = []
for i in range(len(data)):
  for j in range(len(data) - 1):
    for k in range(len(data) - 2):
      jData = listExcludedIndices(data, [i])
      kData = listExcludedIndices(jData, [j])
      result.append([data[i], jData[j], kData[k]])

Doppelte Kombination

Kombinationen mit Überlappung

1. Sie können herausnehmen, was Sie einmal herausgenommen haben, und es wieder herausnehmen
2. Die Reihenfolge der Extraktion ist nicht sinnvoll (wenn die Elemente, aus denen die Menge besteht, gleich sind, werden sie auch dann als gleich behandelt, wenn die Reihenfolge unterschiedlich ist).

Das ist. Betrachten wir 2. im Detail. Wenn die angegebenen Daten "[1,2,3,4]" sind, dann sind "[1,1,2]" und "[1,2,1]" und "[2,1,1]" Es ist das gleiche. Mit anderen Worten, wenn Sie im Gegensatz zur Reihenfolge mit Duplikaten alle Paare finden, die 1 enthalten, müssen Sie danach nicht die Paare finden, die 1 enthalten. Um dies zu erreichen, können Sie die Startposition der verschachtelten Schleife verschieben. Ich denke, es kann wie folgt ausgedrückt werden.

1. Schleife für das erste Element
2. Eine Schleife, die ein zweites Element sucht, das in der ersten Schleife verschachtelt ist Es beginnt jedoch an der Position, die in der ersten Schleife eingenommen wurde.
3. Schleife, um das dritte Element zu finden, das in der zweiten Schleife verschachtelt ist Es beginnt jedoch an der Position, die in der zweiten Schleife eingenommen wurde.

Das Programm ist wie folgt.

result = []
for i in range(len(data)):
  for j in range(i, len(data)):
    for k in range(j, len(data)):
      result.append([data[i], data[j], data[k]])

Kombination

Die Kombination ist

1. Ich kann nicht herausnehmen, was ich einmal herausgenommen habe
2. Die Reihenfolge der Extraktion ist nicht sinnvoll (wenn die Elemente, aus denen die Menge besteht, gleich sind, werden sie auch dann als gleich behandelt, wenn die Reihenfolge unterschiedlich ist).

Das ist. Daher ist der Prozess des Findens eines Satzes wie beim Finden der Sequenz wie folgt.

1. Extrahieren Sie eine aus den Daten
2. Nehmen Sie einen aus dem Rest heraus, außer dem, der in 1 herausgenommen wurde.
3. Nehmen Sie einen aus dem Rest heraus, außer dem, der in 1-2 herausgenommen wurde.

Sie können die Position der Schleife auf dieselbe Weise verschieben wie die Kombination mit Überlappung. Lassen Sie uns ein Programm erstellen, das auf der obigen Idee basiert.

result = []
for i in range(len(data)):
  for j in range(i, len(data) - 1):
    for k in range(j, len(data) - 2):
      jData = listExcludedIndices(data, [i])
      kData = listExcludedIndices(jData, [j])
      result.append([data[i], jData[j], kData[k]])

Es gibt jedoch Duplikate

1. Schleife für das erste Element
2. Eine Schleife, die ein zweites Element sucht, das in der ersten Schleife verschachtelt ist Es beginnt jedoch an der Position, die in der ersten Schleife eingenommen wurde.
3. Schleife, um das dritte Element zu finden, das in der zweiten Schleife verschachtelt ist Es beginnt jedoch an der Position, die in der zweiten Schleife eingenommen wurde.

Der Zweck bestand darin, die Vervielfältigung zuzulassen. Wenn Sie also keine Vervielfältigung zulassen,

1. Schleife für das erste Element
2. Eine Schleife, die ein zweites Element sucht, das in der ersten Schleife verschachtelt ist Es beginnt jedoch nach der Position in der ersten Schleife.
3. Schleife, um das dritte Element zu finden, das in der zweiten Schleife verschachtelt ist Es beginnt jedoch nach der Position in der zweiten Schleife.

Kann sein. Mit anderen Worten kann das Programm wie folgt umgeschrieben werden.

result = []
for i in range(len(data)):
  for j in range(i + 1, len(data)):
    for k in range(j + 1, len(data)):
      result.append([data[i], data[j], data[k]])

Sie können es auch erhalten, indem Sie Duplikate aus Kombinationen mit Duplikaten entfernen, z. B. Vorwärtsspalten und Vorwärtsspalten mit Duplikaten.

Verwenden Sie rekursiv

In den oben genannten Programmen wurde r behoben. Da es so wie es ist nutzlos ist, wird es zu einer Funktion gemacht. Konvertieren Sie zunächst das, was Sie auf feste Weise geschrieben haben, in rekursiv. Jedes hat eine Struktur, in der eine Schleife, die sich n-mal wiederholt, r-mal verschachtelt ist. Es scheint, dass die Verschachtelung durch einen rekursiven Aufruf realisiert werden sollte und n Schleifen durch einen rekursiven Aufruf realisiert werden sollten. Wenn Sie dann die Endbedingung der Wiederholung auf 0 setzen, wenn r zu 0 wird, können Sie sie in rekursiv konvertieren.

Rekursive Version mit Duplikaten

Im Fall einer Sequenz mit Duplikaten ist die einfachste wie folgt. Der in einem Aufruf erhaltene Wert wird als Fortschritt betrachtet und dieser Wert minus r wird an den nächsten rekursiven Aufruf übergeben. Wenn r 0 wird, speichern Sie den Inhalt des Fortschritts, um das Ergebnis zu erhalten, und beenden Sie das Programm. Die Funktion, die das Element tatsächlich findet, muss einen Anfangswert angeben. Da es so schwierig zu bedienen ist, definiere ich eine Wrapper-Funktion und rufe sie auf.

def permutationWithRepetitionListRecursive(data, r):
  if r <= 0:
    return []

  result = []
  _permutationWithRepetitionListRecursive(data, r, [], result)
  return result

def _permutationWithRepetitionListRecursive(data, r, progress, result):
  if r == 0:
    result.append(progress)
    return

  for i in range(len(data)):
    _permutationWithRepetitionListRecursive(data, r - 1, progress + [data[i]], result)

Rekursiv sequentiell

Da die Sequenz keine erneute Extraktion erlaubt, kann sie durch Hinzufügen der Verarbeitung erhalten werden. In der Auftragsspalte mit Duplikaten wurden die Daten unverändert an den nächsten Aufruf übergeben. Hier wird jedoch der Rest mit Ausnahme des einmal abgerufenen übergeben.

def permutationListRecursive(data, r):
  if r <= 0 or r > len(data):
    return []

  result = []
  _permutationListRecursive(data, r, [], result)
  return result

def _permutationListRecursive(data, r, progress, result):
  if r == 0:
    result.append(progress)
    return

  for i in range(len(data)):
    _permutationListRecursive(listExcludedIndices(data, [i]), r - 1, progress + [data[i]], result)

Rekursive Version mit doppelter Kombination

Fügen Sie für doppelte Kombinationen ein Argument hinzu, das die Startposition darstellt, geben Sie diesem Argument die aktuelle Abrufposition und führen Sie den nächsten rekursiven Aufruf aus. Ansonsten gibt es keinen Unterschied zur Bestellung mit Duplikaten.

def combinationWithRepetitionListRecursive(data, r):
  if r <= 0:
    return []

  result = []
  _combinationWithRepetitionListRecursive(data, r, 0, [], result)
  return result

def _combinationWithRepetitionListRecursive(data, r, start, progress, result):
  if r == 0:
    result.append(progress)
    return

  for i in range(start, len(data)):
    _combinationWithRepetitionListRecursive(data, r - 1, i, progress + [data[i]], result)

Rekursive Versionskombination

Die Kombination stellt sicher, dass der nächste rekursive Aufruf der aktuellen Abrufposition einen Schritt voraus ist.

def combinationListRecursive(data, r):
  if r == 0 or r > len(data):
    return []

  result = []
  _combinationListRecursive(data, r, 0, [], result)
  return result


def _combinationListRecursive(data, r, start, progress, result):
  if r == 0:
    result.append(progress)
    return

  for i in range(start, len(data)):
    #Eine andere Lösung_combinationListRecursive(listExcludedIndices(data, [i]), r - 1, i, progress + [data[i]], result)
    _combinationListRecursive(data, r - 1, i + 1, progress + [data[i]], result)

Verwenden Sie Schleifen

Der Empfang ist gefährlich, da er einen Stapelüberlauf verursachen kann. Betrachten Sie daher eine Funktion, die Schleifen verwendet. Grundsätzlich sind r-Schleifen erforderlich, um ein Element zu finden, und Sie müssen es nur so oft wiederholen, wie Sie benötigen. Die Gesamtzahl von jedem wird sofort offiziell berechnet, also benutze das. Darüber hinaus erwägen wir im Folgenden eine Lösungsmethode, die auf der Position (dem Index) basiert, um alle herauszunehmen.

Loop-Version mit Duplikaten

Wenn n = 4 und r = 3 ist, ist die Reihenfolge mit den zu erhaltenen Duplikaten wie folgt.

00: 0 0 0 -> data[0] data[0] data[0]
01: 0 0 1 -> data[0] data[0] data[1]
02: 0 0 2 -> data[0] data[0] data[2]
03: 0 0 3 -> data[0] data[0] data[3]
04: 0 1 0 -> data[0] data[1] data[0]
05: 0 1 1 -> data[0] data[1] data[1]
06: 0 1 2 -> data[0] data[1] data[2]
07: 0 1 3 -> data[0] data[1] data[3]
08: 0 2 0 -> data[0] data[1] data[0]
09: 0 2 1 -> data[0] data[1] data[1]
10: 0 2 2 -> data[0] data[1] data[2]
11: 0 2 3 -> data[0] data[1] data[3]
...

Die Reihenfolge mit Duplikaten entspricht der Ermittlung der Anzahl der r-Stellen. Wenn die Anzahl der Ziffern durch d dargestellt wird, zählt jede Ziffer jedes "n ^ d" auf die gleiche Weise wie eine n-fache Zahl hoch. Wenn Sie jetzt ein Element durch i darstellen, können Sie den Index dieser Ziffer finden, indem Sie i durch n ^ d teilen. Dies überschreitet die Größe der Daten, daher müssen Sie sie als Rest durch n teilen. Das Programm sieht folgendermaßen aus:

import math

def permutationWithRepetition(n, r):
  return int(pow(n, r))


def permutationWithRepetitionList(data, r):
  length = len(data)
  total = permutationWithRepetition(length, r)
  result = []
  for i in range(total):
    element = []
    for digit in reversed(range(r)):
      element.append(data[int(i / pow(length, digit)) % length])
    result.append(element)
  return result

Loop-Version sequentiell

Wenn n = 4 und r = 3 ist, ist die zu erhaltende Reihenfolge wie folgt.

00: 0 1 2 -> data[0] data[1] data[2]
01: 0 1 3 -> data[0] data[1] data[3]
02: 0 2 1 -> data[0] data[2] data[1]
03: 0 2 3 -> data[0] data[2] data[3]
04: 0 3 1 -> data[0] data[3] data[1]
05: 0 3 2 -> data[0] data[3] data[2]
06: 1 0 2 -> data[1] data[0] data[2]
07: 1 0 3 -> data[1] data[0] data[3]
08: 1 2 0 -> data[1] data[2] data[0]
09: 1 2 3 -> data[1] data[2] data[3]
10: 1 3 0 -> data[1] data[3] data[0]
11: 1 3 2 -> data[1] data[3] data[2]
12: 2 0 1 -> data[2] data[0] data[1]
13: 2 0 3 -> data[2] data[0] data[3]
14: 2 1 0 -> data[2] data[1] data[0]
15: 2 1 3 -> data[2] data[1] data[3]
16: 2 3 0 -> data[2] data[3] data[0]
17: 2 3 1 -> data[2] data[3] data[1]
18: 3 0 1 -> data[3] data[0] data[1]
19: 3 0 2 -> data[3] data[0] data[2]
20: 3 1 0 -> data[3] data[1] data[0]
21: 3 1 2 -> data[3] data[1] data[2]
22: 3 2 0 -> data[3] data[2] data[0]
23: 3 2 1 -> data[3] data[2] data[2]

Dies wird wahrscheinlich auch aus der Elementnummer i und der Ziffer d erhalten.

Betrachten Sie zunächst die dritte Ziffer. Die gleiche Zahl erscheint von 1 bis 4. Mit anderen Worten, wenn Sie P (n, r) durch n teilen, können Sie die Position finden, die hochgezählt werden soll.

Betrachten Sie die zweite Ziffer. Hier erscheinen andere Zahlen als die in der dritten Ziffer. Die Gesamtzahl ist n-1. Dies wird gleichmäßig angezeigt, wenn die dritte Ziffer dieselbe Nummer ist. Mit anderen Worten, P (n, r) / (n \ * n-1) zählt hoch.

Wenn Sie die erste Ziffer auf die gleiche Weise betrachten, können Sie sehen, dass sie mit P (n, r) / (n \ * n-1 \ * n-2) zählt.

Lassen Sie uns aus der obigen Idee ein Programm machen.

import math
import functools
import operator

def permutation(n, r):
  if(n < r):
    return 0
  return int(math.factorial(n) / math.factorial(n - r))

def permutationList(data, r):
  length = len(data)
  total = permutation(length, r)
  result = []
  for i in range(total):
    element = []
    copyData = data[:]
    for digit in range(r):
      l = len(copyData)
      countUp = total / functools.reduce(operator.mul, range(l, length + 1))
      index = int(i / countUp) % l
      element.append(copyData.pop(index))
    result.append(element)
  return result

Loop-Version mit Duplikationskombination

Wenn n = 4 und r = 3 ist, ist die Kombination mit der zu erhaltenen Verdoppelung wie folgt.

00: 0 0 0 -> data[0] data[0] data[0]
01: 0 0 1 -> data[0] data[0] data[1]
02: 0 0 2 -> data[0] data[0] data[2]
03: 0 0 3 -> data[0] data[0] data[3]
04: 0 1 1 -> data[0] data[1] data[1]
05: 0 1 2 -> data[0] data[1] data[2]
06: 0 1 3 -> data[0] data[1] data[3]
07: 0 2 2 -> data[0] data[2] data[2]
08: 0 2 3 -> data[0] data[2] data[3]
09: 0 3 3 -> data[0] data[3] data[3]
10: 1 1 1 -> data[1] data[1] data[1]
11: 1 1 2 -> data[1] data[1] data[2]
12: 1 1 3 -> data[1] data[1] data[3]
13: 1 2 2 -> data[1] data[2] data[2]
14: 1 2 3 -> data[1] data[2] data[3]
15: 1 3 3 -> data[1] data[3] data[3]
16: 2 2 2 -> data[2] data[2] data[2]
17: 2 2 3 -> data[2] data[2] data[3]
18: 2 3 3 -> data[2] data[3] data[3]
19: 3 3 3 -> data[3] data[3] data[3]

Dies scheint anhand der Elementnummer schwer zu finden zu sein. Versuchen Sie daher, das nächste Element aus dem vorherigen Element zu finden. Wenn Sie sich auf die 1. Ziffer konzentrieren, ist der vorherige Wert +1, außer wenn die 2. oder 3. Ziffer geändert wurde. Daher scheint es, dass es gesteuert werden kann, indem der Count-up der 2. und 3. Stelle erfasst wird. Wenn Sie die Stelle extrahieren, an der die zweite Ziffer zählt,

0 0 3 -> 0 1 1
0 1 3 -> 0 2 2
0 2 3 -> 0 3 3

Was sie gemeinsam haben, ist

• Die erste Ziffer des vorherigen Elements ist 3
• Die zweite Ziffer wird um +1 erhöht
• Die erste und die zweite Ziffer sind gleich

ist. Wenn Sie die Stelle extrahieren, an der die dritte Ziffer zählt,

0 3 3 -> 1 1 1
1 3 3 -> 2 2 2
2 3 3 -> 3 3 3

Was sie gemeinsam haben, ist

• Die zweite Ziffer des vorherigen Elements ist 3
• Die dritte Ziffer wird um +1 erhöht
• Die dritte, zweite und erste Ziffer sind gleich

ist.

Wenn Sie dies in eine Funktion setzen

--N-1 kommt zur i-Stelle des vorherigen Elements --i + 1 addiere +1 zur ersten Ziffer

• Machen Sie i + 1 Ziffern und später die gleichen wie i + 1 Ziffern

Es wird gut sein. Es ist ein chaotisches Programm, aber es sieht so aus: Hier wird die Funktion getListElements definiert und verwendet, die den Wert aus dem Indexsatz erhält.

def getListElements(lis, indices):
  """Gibt den Satz von Elementen zurück, die durch Indies aus der Liste angezeigt werden"""
  return [lis[i] for i in indices]

import math

def combinationWithRepetition(n, r):
  return int(math.factorial(r + n - 1) / (math.factorial(r) * math.factorial(n - 1)))

def updateCombinationIndex(lastIndex, start, repetition=False):
  result = lastIndex[:start]
  x = lastIndex[start] + 1
  for i in range(start, len(lastIndex)):
    result.append(x)
    if(repetition == False):
      x += 1
  return result

def getComginationWithRepetitionIndex(length, r, lastIndex):
  result = []
  for i in range(r):
    if(len(lastIndex) == 0):
      result.append(0)
    elif(lastIndex[i] >= length - 1):
      result = updateCombinationIndex(lastIndex, i - 1, True)
      break
    elif(i == r - 1):
      result = updateCombinationIndex(lastIndex, i, True)
  return result

def combinationWithRepetitionList(data, r):
  length = len(data)
  total = combinationWithRepetition(length, r)
  result = []
  lastIndex = []
  for i in range(total):
    lastIndex = getComginationWithRepetitionIndex(length, r, lastIndex)
    result.append(getListElements(data, lastIndex))
  return result

Loop-Versionskombination

Wenn n = 4 und r = 3 ist, ist die zu erhaltende Kombination wie folgt.

00: 0 1 2 -> data[0] data[1] data[2]
01: 0 1 3 -> data[0] data[1] data[3]
02: 0 2 3 -> data[0] data[2] data[3]
03: 1 2 3 -> data[1] data[2] data[3]

Ich werde versuchen, es auf die gleiche Weise zu finden wie die Kombination mit der Vervielfältigung. Es ist schwer zu verstehen, da es nur wenige konkrete Beispiele gibt, aber der Ort, an dem die zweite Ziffer zählt, ist

• Die erste Ziffer des vorherigen Elements ist 3
• Die zweite Ziffer wird um +1 erhöht ――Die erste Ziffer wird zur zweiten Ziffer +1

Der Ort, an dem die dritte Ziffer zählt, ist

• Die zweite Ziffer des vorherigen Elements ist 2
• Die dritte Ziffer wird um +1 erhöht ――Die zweite Ziffer wird zur dritten Ziffer +1 ――Die erste Ziffer wird zur zweiten Ziffer +1

Es ist genauso wie das.

--N-i kommt zur i-Ziffer des vorherigen Elements --i + 1 addiere +1 zur ersten Ziffer --i + 1 - Setze die n-te Ziffer auf das Element von i + 1 + n

Wenn Sie die Bedingungen für das Aufzählen und die Änderungen ändern, können Sie dies auf die gleiche Weise wie in Kombination mit der Duplizierung vornehmen. Das Programm sieht folgendermaßen aus:

import math

def combination(n, r):
  if(n < r):
    return 0
  return int(math.factorial(n) / (math.factorial(r) * math.factorial(n - r)))

def getComginationIndex(length, r, lastIndex):
  result = []
  for i in range(r):
    if(len(lastIndex) == 0):
        result.append(i)
    elif(lastIndex[i] >= length - r + i):
      result = updateCombinationIndex(lastIndex, i - 1, False)
      break
    elif(i == r - 1):
      result = updateCombinationIndex(lastIndex, i, False)
  return result

def combinationList(data, r):
  length = len(data)
  total = combination(length, r)
  result = []
  lastIndex = []
  for i in range(total):
    lastIndex = getComginationIndex(length, r, lastIndex)
    result.append(getListElements(data, lastIndex))
  return result

Generator

Da ich es mit Python gemacht habe, werde ich es als Generator versuchen. Ich weiß, dass die rekursive Version des Generators funktioniert, wenn ich es so schreibe, aber ich bin mir nicht sicher, warum ich es tun soll. Es ist auch nicht bekannt, dass der Speicher usw. überlastet wird, wenn die Operation in einem tiefen Stapel mit dem rekursiven Versionsgenerator gestoppt wird.

Rekursive Generatorversion Doppelte Bestellung

Wenn Sie es nur mit "Ertrag" erstellen, ist es wie folgt. Es ist "Ausbeute", einen Wert zurückzugeben, wenn r 0 ist, und da die rekursive Funktion selbst eine Generalta zurückgibt, wird sie mit einer "for" -Anweisung gedreht, um sie zu drehen. Ich habe versucht, die an die rekursive Funktion übergebenen Daten als Generator zu verwenden, konnte sie jedoch aufgrund der bisherigen Schwierigkeiten nicht realisieren.

def permutationWithRepetitionGeneratorRecursive(data, r):
  if r <= 0:
    return []

  return _permutationWithRepetitionGeneratorRecursive(data, r, [])

def _permutationWithRepetitionGeneratorRecursive(data, r, progress):
  if r == 0:
    yield progress
    return

  for i in range(len(data)):
    for j in _permutationWithRepetitionGeneratorRecursive(data, r - 1, progress + [data[i]]):
      yield j

Mit "Ausbeute von" erhalten wir: Es kamen zwei Erträge heraus und es war nicht launisch, also fühlt es sich gut und erfrischend an.

def _permutationWithRepetitionGeneratorRecursive(data, r, progress):
  if r == 0:
    yield progress
    return

  for i in range(len(data)):
    yield from _permutationWithRepetitionGeneratorRecursive(data, r - 1, progress + [data[i]])

Rekursive Generatorversion sequentiell

def permutationGeneratorRecursive(data, r):
  if r <= 0 or r > len(data):
    return []

  return _permutationGeneratorRecursive(data, r, [])

def _permutationGeneratorRecursive(data, r, progress):
  if r == 0:
    yield progress
    return

  for i in range(len(data)):
    yield from _permutationGeneratorRecursive(listExcludedIndices(data, [i]), r - 1, progress + [data[i]])

Rekursive Generatorversion Doppelte Kombination

def combinationWithRepetitionGeneratorRecursive(data, r):
  if r <= 0:
    return []

  return _combinationWithRepetitionGeneratorRecursive(data, r, 0, [])

def _combinationWithRepetitionGeneratorRecursive(data, r, start, progress):
  if r == 0:
    yield progress
    return

  for i in range(start, len(data)):
    yield from _combinationWithRepetitionGeneratorRecursive(data, r - 1, i, progress + [data[i]])

Rekursive Generatorversionskombination

def combinationGeneratorRecursive(data, r):
  if r == 0 or r > len(data):
    return []

  return _combinationGeneratorRecursive(data, r, 0, [])

def _combinationGeneratorRecursive(data, r, start, progress):
  if r == 0:
    yield progress
    return

  for i in range(start, len(data)):
    yield from _combinationGeneratorRecursive(data, r - 1, i + 1, progress + [data[i]])

Schleifengeneratorversion Doppelte Bestellung

def permutationWithRepetitionGenerator(data, r):
  length = len(data)
  total = permutationWithRepetition(length, r)
  for i in range(total):
    element = []
    for digit in reversed(range(r)):
      element.append(data[int(i / pow(length, digit)) % length])
    yield element

Schleifengeneratorversion sequentiell

def permutationGenerator(data, r):
  length = len(data)
  total = permutation(length, r)
  for i in range(total):
    element = []
    copyData = data[:]
    for digit in range(r):
      l = len(copyData)
      countUp = total / functools.reduce(operator.mul, range(l, length + 1))
      index = int(i / countUp) % l
      element.append(copyData.pop(index))
    yield element

Schleifengeneratorversion mit Duplikationskombination

def combinationWithRepetitionGenerator(data, r):
  length = len(data)
  total = combinationWithRepetition(length, r)
  lastIndex = []
  for i in range(total):
    lastIndex = getComginationWithRepetitionIndex(length, r, lastIndex)
    yield getListElements(data, lastIndex)

Kombination der Schleifengeneratorversionen

def combinationGenerator(data, r):
  length = len(data)
  total = combination(length, r)
  lastIndex = []
  for i in range(total):
    lastIndex = getComginationIndex(length, r, lastIndex)
    yield getListElements(data, lastIndex)

Schließlich

Es ist schwierig in Worten. Anstatt über die Theorie / Lösung nachzudenken und sie dann zu einem Programm zu machen, hatte ich das Gefühl, an eine Lösung / Theorie aus dem Programm zu denken, daher war der Text nicht sehr gut. Darüber hinaus gibt es Stellen, an denen Erklärungen übersprungen werden. Ein solcher Ort ist ein Ort, an dem ich nicht genug verstanden habe oder mich gefragt habe, was ich mit dem Ausdruck anfangen soll.

Referenz Beispiel für eine Python-Dokumentation

def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

def combinations(iterable, r):
    pool = tuple(iterable)
    n = len(pool)
    for indices in permutations(range(n), r):
        if sorted(indices) == list(indices):
            yield tuple(pool[i] for i in indices)

def combinations_with_replacement(iterable, r):
    # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC
    pool = tuple(iterable)
    n = len(pool)
    if not n and r:
        return
    indices = [0] * r
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != n - 1:
                break
        else:
            return
        indices[i:] = [indices[i] + 1] * (r - i)
        yield tuple(pool[i] for i in indices)

def combinations_with_replacement(iterable, r):
    pool = tuple(iterable)
    n = len(pool)
    for indices in product(range(n), repeat=r):
        if sorted(indices) == list(indices):
            yield tuple(pool[i] for i in indices)

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    for indices in product(range(n), repeat=r):
        if len(set(indices)) == r:
            yield tuple(pool[i] for i in indices)

def product(*args, repeat=1):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = [tuple(pool) for pool in args] * repeat
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)