Implémentation Python pour next_permutation dans STL

Question

next_permutation est une fonction C++ qui donne la permutation lexicographiquement suivante d'une chaîne. Des détails sur sa mise en œuvre peuvent être obtenus à partir de ce poste vraiment génial. http://wordaligned.org/articles/next-permutation

1. t-il quelqu'un au courant d'une mise en œuvre similaire en Python?
2. Existe-t-il un équivalent python direct pour les itérateurs STL?

Answer 1

1. itertools.permutations est proche; La plus grande différence est qu'il traite tous les éléments comme uniques plutôt que de les comparer. Il ne modifie pas non plus la séquence en place. Implémenter std :: next_permutation en Python pourrait être un bon exercice pour vous (utilisez l'indexation sur une liste plutôt que sur les itérateurs à accès aléatoire). Les itérateurs Python sont comparables aux itérateurs d'entrée, qui sont une catégorie STL, mais seulement la pointe de cet iceberg. Vous devez utiliser à la place d'autres constructions, telles qu'un appelable pour un itérateur de sortie. Cela casse la bonne syntaxe générale des itérateurs C++.

Answer 2

itertools semble être ce dont vous avez besoin.

Answer 3

Une mise en œuvre du lexicographique-allié de permutation suivante en Python (reference)

def lexicographically_next_permutation(a): 
    """ 
    Generates the lexicographically next permutation. 

    Input: a permutation, called "a". This method modifies 
    "a" in place. Returns True if we could generate a next 
    permutation. Returns False if it was the last permutation 
    lexicographically. 
    """ 
    i = len(a) - 2 
    while not (i < 0 or a[i] < a[i+1]): 
     i -= 1 
    if i < 0: 
     return False 
    # else 
    j = len(a) - 1 
    while not (a[j] > a[i]): 
     j -= 1 
    a[i], a[j] = a[j], a[i]  # swap 
    a[i+1:] = reversed(a[i+1:]) # reverse elements from position i+1 till the end of the sequence 
    return True 

Answer 4

est ici un simple Python 3 mise en œuvre de wikipedia's algorithm for generating permutations in lexicographic order:

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 

Elle produit les mêmes résultats que std::next_permutation() en C++.

Answer 5

Une mise en œuvre prolixe de this approche sur ordre 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))