Python-Implementierung für next_permutation in STL

Python-Implementierung für next_permutation in STL
  1. itertools.permutations ist in der Nähe; Der größte Unterschied besteht darin, dass alle Elemente als einzigartig behandelt werden, anstatt sie zu vergleichen. Es ändert auch nicht die Sequenz an Ort und Stelle. Die Implementierung von std::next_permutation in Python könnte eine gute Übung für Sie sein (verwenden Sie die Indizierung auf einer Liste statt Iteratoren mit wahlfreiem Zugriff).

  2. Nein. Python-Iteratoren sind vergleichbar mit Eingabe-Iteratoren, die eine STL-Kategorie sind, aber nur die Spitze dieses Eisbergs. Stattdessen müssen Sie andere Konstrukte verwenden, z. B. ein Callable für einen Ausgabe-Iterator. Dies bricht die nette Syntax-Allgemeinheit von C++-Iteratoren.


Hier ist eine einfache Python 3-Implementierung des Wikipedia-Algorithmus zum Generieren von Permutationen in lexikografischer Reihenfolge:

def next_permutation(a):
 """Generate the lexicographically next permutation inplace.

 https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
 Return false if there is no next permutation.
 """
 # Find the largest index i such that a[i] < a[i + 1]. If no such
 # index exists, the permutation is the last permutation
 for i in reversed(range(len(a) - 1)):
 if a[i] < a[i + 1]:
 break # found
 else: # no break: not found
 return False # no next permutation

 # Find the largest index j greater than i such that a[i] < a[j]
 j = next(j for j in reversed(range(i + 1, len(a))) if a[i] < a[j])

 # Swap the value of a[i] with that of a[j]
 a[i], a[j] = a[j], a[i]

 # Reverse sequence from a[i + 1] up to and including the final element a[n]
 a[i + 1:] = reversed(a[i + 1:])
 return True

Es erzeugt dieselben Ergebnisse wie std::next_permutation() in C++, außer dass es die Eingabe nicht in die lexikografisch erste Permutation umwandelt, wenn es keine weiteren Permutationen gibt.


itertools scheint genau das zu sein, was Sie brauchen.