Given a string S, the task is to print permutations of all words in a sentence.
Examples:
Input: S = “sky is blue”
Output:
sky is blue
sky blue is
is sky blue
is blue sky
blue sky is
blue is skyInput: S =” Do what you love”
Output:
Do what you love
Do what love you
Do you what love
Do you love what
Do love what you
Do love you what
what Do you love
what Do love you
what you Do love
what you love Do
what love Do you
what love you Do
you Do what love
you Do love what
you what Do love
you what love Do
you love Do what
you love what Do
love Do what you
love Do you what
love what Do you
love what you Do
love you Do what
love you what Do
Approach: The given problem can be solved using recursion. Follow the steps below to solve the problem:
- Traverse the sentence and split the words present in the sentence by spaces using split() and store them in a list.
- Permute the list using built-in python functions itertools.permutations().
- Traverse the permutations and convert each permutation to a list.
- Print these lists.
Below is the implementation of the above approach:
Java
import java.util.*;public class Main { // Function to generate permutations // of all words in a sentence public static void calculatePermutations(String sentence) { // Stores all words in the sentence String[] lis = sentence.split(" "); // Stores all possible permutations // of words in this list Iterable<String[]> permute = permuteGenerator(lis); // Iterate over all permutations for (String[] i : permute) { // Print the words in the // list separated by spaces System.out.println(String.join(" ", i)); } } // Function to generate permutations using generators public static Iterable<String[]> permuteGenerator(String[] arr) { return permuteGenerator(arr, arr.length); } public static Iterable<String[]> permuteGenerator(String[] arr, int n) { if (n <= 1) { List<String[]> result = new ArrayList<>(); result.add(Arrays.copyOf(arr, arr.length)); return result; } else { List<String[]> result = new ArrayList<>(); for (String[] i : permuteGenerator(arr, n - 1)) { result.add(Arrays.copyOf(i, i.length)); } for (int i = 0; i < n - 1; i++) { if (n % 2 == 0) { String temp = arr[i]; arr[i] = arr[n - 1]; arr[n - 1] = temp; } else { String temp = arr[0]; arr[0] = arr[n - 1]; arr[n - 1] = temp; } for (String[] k : permuteGenerator(arr, n - 1)) { result.add(Arrays.copyOf(k, k.length)); } } return result; } } // Driver Code public static void main(String[] args) { String sentence = "sky is blue"; calculatePermutations(sentence); }} |
Python3
# Python implementation of# the above approachfrom itertools import permutations# Function to generate permutations# of all words in a sentencedef 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 Codeif __name__ == '__main__': sentence = "sky is blue" calculatePermutations(sentence) |
C#
using System;using System.Collections.Generic;class MainClass { // Function to generate permutations // of all words in a sentence static void calculatePermutations(string sentence) { // Stores all words in the sentence string[] lis = sentence.Split(' '); // Stores all possible permutations // of words in this list IEnumerable<string[]> permute = permuteGenerator(lis); // Iterate over all permutations foreach(string[] i in permute) { // Print the words in the // list separated by spaces Console.WriteLine(string.Join(" ", i)); } } // Function to generate permutations using generators static IEnumerable<string[]> permuteGenerator(string[] arr, int n = -1) { if (n == -1) n = arr.Length; if (n <= 1) { yield return arr; } else { for (int i = 0; i < n; i++) { foreach(string[] k in permuteGenerator( arr, n - 1)) { yield return k; } int j = n % 2 != 0 ? 0 : i; string temp = arr[j]; arr[j] = arr[n - 1]; arr[n - 1] = temp; } } } // Driver Code public static void Main(string[] args) { string sentence = "sky is blue"; calculatePermutations(sentence); }}// This code is contributed by user_dtewbxkn77n |
Javascript
// JavaScript implementation of// the above approach// Function to generate permutations// of all words in a sentencefunction calculatePermutations(sentence) { // Stores all words in the sentence let lis = sentence.split(" "); // Stores all possible permutations // of words in this list let permute = permuteGenerator(lis); // Iterate over all permutations for (let i of permute) { // Print the words in the // list separated by spaces console.log(i.join(" ")); }}// Function to generate permutations using generatorsfunction* permuteGenerator(arr, n = arr.length) { if (n <= 1) yield arr.slice(); else for (let i = 0; i < n; i++) { yield* permuteGenerator(arr, n - 1); const j = n % 2 ? 0 : i; [arr[n - 1], arr[j]] = [arr[j], arr[n - 1]]; }}// Driver Codelet sentence = "sky is blue";calculatePermutations(sentence);// This code is contributed by adityashae15 |
Output:
sky is blue sky blue is is sky blue is blue sky blue sky is blue is sky
Time Complexity: O(N!), where N denotes the number of words in a sentence.
Auxiliary Space: O(N!)
Another Approach: Using Backtracking:
- Traverse the sentence and split the words present in the sentence by spaces using split() and store them in a list.
- Initialize an empty list to store the permutations of the words.
- Start a backtracking function to generate all possible permutations of the words list. The function will take the following parameters:
.The current list of words.
.The index of the word that needs to be swapped with the remaining words.
.The list to store the permutations of the words.
- If the current index is equal to the length of the words list, then add the current permutation to the list of permutations.
- Iterate over the remaining words from the current index to the end of the list, swapping the current word with each remaining word and making a recursive call to the backtracking function with the updated list and index.
- After the recursive call, swap back the current word with the previously swapped word.
- Return the list of permutations after all recursive calls have been made.
Below is the implementation of the above approach:
Java
import java.util.*;public class Main { // Function to generate permutations // of all words in a sentence public static void calculatePermutations(String sentence) { // Stores all words in the sentence String[] lis = sentence.split(" "); // Stores all possible permutations // of words in this list List<String[]> permute = new ArrayList<>(); // Generate all permutations of words generatePermutations(lis, 0, permute); // Iterate over all permutations for (String[] i : permute) { // Print the words in the // list separated by spaces System.out.println(String.join(" ", i)); } } // Function to generate all permutations using // backtracking public static void generatePermutations(String[] arr, int index, List<String[]> permute) { // Base case: If the current index is equal to the // length of the array add the current permutation // to the list of permutations if (index == arr.length) { permute.add(Arrays.copyOf(arr, arr.length)); return; } // Iterate over the remaining words and generate // permutations for (int i = index; i < arr.length; i++) { // Swap the current word with the ith word String temp = arr[i]; arr[i] = arr[index]; arr[index] = temp; // Make a recursive call to generate // permutations with the updated list and index generatePermutations(arr, index + 1, permute); // Swap back the current word with the // previously swapped word temp = arr[i]; arr[i] = arr[index]; arr[index] = temp; } } // Driver Code public static void main(String[] args) { String sentence = "sky is blue"; calculatePermutations(sentence); }}// This code is contributed by sarojmcy2e |
Python3
from typing import List# Function to generate permutations of all words in a sentencedef calculatePermutations(sentence: str) -> None: # Stores all words in the sentence lis = sentence.split(" ") # Stores all possible permutations of words in this list permute = [] # Generate all permutations of words generatePermutations(lis, 0, permute) # Iterate over all permutations for i in permute: # Print the words in the list separated by spaces print(" ".join(i))# Function to generate all permutations using backtrackingdef generatePermutations(arr: List[str], index: int, permute: List[List[str]]) -> None: # Base case: If the current index is equal to the length of the array, # add the current permutation to the list of permutations if index == len(arr): permute.append(arr.copy()) return # Iterate over the remaining words and generate permutations for i in range(index, len(arr)): # Swap the current word with the ith word arr[i], arr[index] = arr[index], arr[i] # Make a recursive call to generate permutations with the updated list and index generatePermutations(arr, index + 1, permute) # Swap back the current word with the previously swapped word arr[i], arr[index] = arr[index], arr[i]# Driver Codeif __name__ == "__main__": sentence = "sky is blue" calculatePermutations(sentence) |
Output
sky is blue sky blue is is sky blue is blue sky blue is sky blue sky is
Time Complexity: O(n! * n), where n is the number of words in the sentence.
Auxiliary Space: O(n! * n), because we are storing all possible permutations of the words in the sentence in a vector of vectors.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
