NEXT_PERMUTATION est une fonction C ++ qui donne la permutation lexicographiquement d'une chaîne. Les détails sur sa mise en œuvre peuvent être obtenus à partir de ce très génial post. http://wordaligned.org/articles/next-Permutation
5 Réponses :
itheroTools.permutations est proche; La plus grande différence est qu'elle traite tous les articles comme uniques plutôt que de les comparer. Il ne modifie pas non plus la séquence en place. Mise en œuvre STD :: Next_permutation à Python pourrait être un bon exercice pour vous (utilisez indexation sur une liste plutôt que des itérateurs d'accès aléatoires).
non. Les itérateurs de Python sont comparables aux itérateurs d'entrée, qui sont une catégorie STL, mais seulement la pointe de cet iceberg. Vous devez plutôt utiliser d'autres constructions, telles qu'une appelable pour un itérateur de sortie. Cela enfreint la belle généralité de la syntaxe des itérateurs C ++.
Ce serait génial si vous pouviez me donner un exemple de Pastebin ou un lien vers un exemple. Merci!
Vous avez mentionné d'autres constructions telles qu'un "appelable d'un opérateur de sortie". Je me demandais si vous pouviez me signaler pour coder des exemples qui démontrent le modèle de conception que vous avez mentionné ci-dessus.
@ZUBIN: Je ne sais rien qui tente de faire passer un appel téléphonique par exemple, mais vous devriez le connaître de C ++, qui utilise une large utilisation des foncteurs.
Une implémentation pour l'allié lexicographique Permutation suivante en Python ( Référence )
Voici une implémentation simple de Python 3 de Algorithme Wikipedia pour générer des permutations dans l'ordre lexicographique : Il produit les mêmes résultats que std :: Next_permutation () en C ++ sauf qu'il ne transforme pas l'entrée dans la première permutation lexicographiquement s'il n'y a pas de plus de permutations.
Il ne produit pas les mêmes résultats que std :: Next_permutation () quand il n'y a pas de permutation suivante (par exemple, lorsque a = ['B', 'A'] Le résultat est différent).
@TAV Vous avez raison, les algorithmes Wikipedia diffèrent de STD :: Next_permutation (ce dernier peut produire une permutation non lexicographiquement: AAB n'est pas la prochaine permutation de BAA : C ++ DOCS: "Transforme sinon la gamme en une première permutation lexicographique"). Les deux fonctions se comportent comme documentées.
Il convient de noter que le même comportement que std :: Next_permutation () peut être obtenu en ajoutant A.Reverse () juste avant retour false .
Une implémentation verbeuse de Cette approche sur la commande lexicographique
def next_permutation(case):
for index in range(1,len(case)):
Px_index = len(case) - 1 - index
#Start travelling from the end of the Data Structure
Px = case[-index-1]
Px_1 = case[-index]
#Search for a pair where latter the is greater than prior
if Px < Px_1 :
suffix = case[-index:]
pivot = Px
minimum_greater_than_pivot_suffix_index = -1
suffix_index=0
#Find the index inside the suffix where ::: [minimum value is greater than the pivot]
for Py in suffix:
if pivot < Py:
if minimum_greater_than_pivot_suffix_index == -1 or suffix[minimum_greater_than_pivot_suffix_index] >= Py:
minimum_greater_than_pivot_suffix_index=suffix_index
suffix_index +=1
#index in the main array
minimum_greater_than_pivot_index = minimum_greater_than_pivot_suffix_index + Px_index +1
#SWAP
temp = case[minimum_greater_than_pivot_index]
case[minimum_greater_than_pivot_index] = case[Px_index]
case[Px_index] = temp
#Sort suffix
new_suffix = case[Px_index+1:]
new_suffix.sort()
#Build final Version
new_prefix = case[:Px_index+1]
next_permutation = new_prefix + new_suffix
return next_permutation
elif index == (len(case) -1):
#This means that this is at the highest possible lexicographic order
return False
#EXAMPLE EXECUTIONS
print("===INT===")
#INT LIST
case = [0, 1, 2, 5, 3, 3, 0]
print(case)
print(next_permutation(case))
print("===CHAR===")
#STRING
case_char = list("dkhc")
case = [ord(c) for c in case_char]
print(case)
case = next_permutation(case)
print(case)
case_char = [str(chr(c)) for c in case]
print(case_char)
print(''.join(case_char))
Il n'est pas recommandé mais vous pouvez appeler std :: Next_permutation à l'aide de
Next_permutation Extension Module écrit à Cyron(il pourrait être utile pour tester / déboguer)