Genere todas las permutaciones posibles de palabras en una oración

Dada una string S , la tarea es imprimir permutaciones de todas las palabras en una oración.

Ejemplos:

Entrada: S = “el cielo es azul”
Salida:  
el cielo es azul
cielo azul es
cielo azul
es cielo azul
cielo azul es
azul es cielo

Entrada: S = «Haz lo que amas»
Salida:
Haz lo que
amas
Haz lo que
amas
Haz
lo que amas
Amas lo Ama lo que Amas lo que Amas lo amor Haz lo que ama _ _ _ _ _ _ _ _ te amo hacer lo que te amo lo que hacer

Enfoque: El problema dado se puede resolver usando recursividad . Siga los pasos a continuación para resolver el problema:

1. Recorra la oración y divida las palabras presentes en la oración por espacios usando split() y guárdelas en una lista.
2. Permute la lista usando las funciones integradas de python itertools.permutations() .
3. Recorra las permutaciones y convierta cada permutación en una lista.
4. Imprima estas listas .

A continuación se muestra la implementación del enfoque anterior:

# Python implementation of
# the above approach
 
from itertools import permutations
 
 
# Function to generate permutations
# of all words in a sentence
def calculatePermutations(sentence):
 
    # Stores all words in the sentence
    lis = list(sentence.split())
 
    # Stores all possible permutations
    # of words in this list
    permute = permutations(lis)
 
    # Iterate over all permutations
    for i in permute:
       
        # Convert the current
        # permutation into a list
        permutelist = list(i)
         
        # Print the words in the
        # list separated by spaces
        for j in permutelist:
            print(j, end = " ")
             
        # Print a new line
        print()
 
 
# Driver Code
if __name__ == '__main__':
 
    sentence = "sky is blue"
    calculatePermutations(sentence)

sky is blue 
sky blue is 
is sky blue 
is blue sky 
blue sky is 
blue is sky

Complejidad de tiempo: O(N!), donde N denota el número de palabras en una oración.
Espacio Auxiliar: O(N!)