Python-implementatie voor next_permutation in STL

Python-implementatie voor next_permutation in STL
  1. itertools.permutaties is dichtbij; het grootste verschil is dat alle items als uniek worden beschouwd in plaats van ze te vergelijken. Het wijzigt ook de volgorde niet op zijn plaats. Het implementeren van std::next_permutation in Python zou een goede oefening voor je kunnen zijn (gebruik indexering op een lijst in plaats van random access iterators).

  2. Nee. Python-iterators zijn vergelijkbaar met input-iterators, die een STL-categorie zijn, maar slechts het topje van die ijsberg. U moet in plaats daarvan andere constructies gebruiken, zoals een oproepbare voor een uitvoeriterator. Dit breekt de mooie syntaxis-algemeenheid van C++ iterators.


Hier is een eenvoudige Python 3-implementatie van wikipedia's algoritme voor het genereren van permutaties in lexicografische volgorde:

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

Het levert dezelfde resultaten op als std::next_permutation() in C++, behalve dat het de invoer niet transformeert in de lexicografisch eerste permutatie als er geen permutaties meer zijn.


itertools lijkt te zijn wat je nodig hebt.