Recursively print all sentences that can be formed from list of word lists
Given a list of word lists How to print all sentences possible taking one word from a list at a time via recursion?
Example:
Input: {{"you", "we"}, {"have", "are"}, {"sleep", "eat", "drink"}} Output: you have sleep you have eat you have drink you are sleep you are eat you are drink we have sleep we have eat we have drink we are sleep we are eat we are drink
We strongly recommend minimizing your browser and try this yourself first.
The idea is based on a simple depth-first traversal. We start from every word of the first list as the first word of an output sentence, then recur for the remaining lists.
Below is the C++ implementation of the above idea. In the below implementation, the input list of the list is considered as a 2D array. If we take a closer look, we can observe that the code is very close to the DFS of graph.
C++
// C++ program to print all possible sentences from a list of word list #include <iostream> #include <string> #define R 3 #define C 3 using namespace std; // A recursive function to print all possible sentences that can be formed // from a list of word list void printUtil(string arr[R][C], int m, int n, string output[R]) { // Add current word to output array output[m] = arr[m][n]; // If this is last word of current output sentence, then print // the output sentence if (m==R-1) { for ( int i=0; i<R; i++) cout << output[i] << " " ; cout << endl; return ; } // Recur for next row for ( int i=0; i<C; i++) if (arr[m+1][i] != "" ) printUtil(arr, m+1, i, output); } // A wrapper over printUtil() void print(string arr[R][C]) { // Create an array to store sentence string output[R]; // Consider all words for first row as starting points and // print all sentences for ( int i=0; i<C; i++) if (arr[0][i] != "" ) printUtil(arr, 0, i, output); } // Driver program to test above functions int main() { string arr[R][C] = {{ "you" , "we" }, { "have" , "are" }, { "sleep" , "eat" , "drink" }}; print(arr); return 0; } |
Java
// Java program to print // all possible sentences // from a list of word list import java.io.*; class GFG{ static final int R= 3 ; static final int C = 3 ; // A recursive function to // print all possible sentences // that can be formed // from a list of word list static void printUtil(String [][]arr, int m, int n, String []output) { // Add current word to output array output[m] = arr[m][n]; // If this is last word of // current output sentence, // then print the output sentence if (m == R - 1 ) { for ( int i = 0 ; i < R; i++) System.out.print(output[i] + " " ); System.out.println(); return ; } // Recur for next row for ( int i = 0 ; i < C; i++) if (arr[m + 1 ][i] != "" && m < C) printUtil(arr, m + 1 , i, output); } // A wrapper over printUtil() static void print(String [][]arr) { // Create an array to store sentence String []output = new String[R]; // Consider all words for first // row as starting points and // print all sentences for ( int i = 0 ; i < C; i++) if (arr[ 0 ][i] != "" ) printUtil(arr, 0 , i, output); } // Driver program to test above functions public static void main(String[] args) { String [][]arr = {{ "you" , "we" , "" }, { "have" , "are" , "" }, { "sleep" , "eat" , "drink" }}; print(arr); } } // This code is contributed by gauravrajput1 |
Python3
# Python program recursively print all sentences that can be # formed from list of word lists R = 3 C = 3 # A recursive function to print all possible sentences that can # be formed from a list of word list def printUtil(arr, m, n, output): # Add current word to output array output[m] = arr[m][n] # If this is last word of current output sentence, then print # the output sentence if m = = R - 1 : for i in range (R): print (output[i],end = " " ) print () return # Recur for next row for i in range (C): if arr[m + 1 ][i] ! = "": printUtil(arr, m + 1 , i, output) # A wrapper over printUtil def printf(arr): # Create an array to store sentence output = [""] * R # Consider all words for first row as starting # points and print all sentences for i in range (C): if arr[ 0 ][i] ! = "": printUtil(arr, 0 , i, output) # Driver program arr = [ [ "you" , "we" ,""], [ "have" , "are" ,""], [ "sleep" , "eat" , "drink" ]] printf(arr) # This code is contributed by Bhavya Jain |
C#
// C# program to print // all possible sentences // from a list of word list using System; class GFG{ static readonly int R= 3; static readonly int C =3; // A recursive function to // print all possible sentences // that can be formed // from a list of word list static void printUtil(String [,]arr, int m, int n, String []output) { // Add current word to output array output[m] = arr[m, n]; // If this is last word of // current output sentence, // then print the output sentence if (m == R - 1) { for ( int i = 0; i < R; i++) Console.Write(output[i] + " " ); Console.WriteLine(); return ; } // Recur for next row for ( int i = 0; i < C; i++) if (arr[m + 1, i] != "" && m < C) printUtil(arr, m + 1, i, output); } // A wrapper over printUtil() static void print(String [,]arr) { // Create an array to store sentence String []output = new String[R]; // Consider all words for first // row as starting points and // print all sentences for ( int i = 0; i < C; i++) if (arr[0, i] != "" ) printUtil(arr, 0, i, output); } // Driver program to test above functions public static void Main(String[] args) { String [,]arr = {{ "you" , "we" , "" }, { "have" , "are" , "" }, { "sleep" , "eat" , "drink" }}; print(arr); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // JavaScript program recursively print all sentences that can be // formed from list of word lists const R = 3 const C = 3 // A recursive function to print all possible sentences that can // be formed from a list of word list function printUtil(arr, m, n, output){ // Add current word to output array output[m] = arr[m][n] // If this is last word of current output sentence, then print // the output sentence if (m == R - 1){ for (let i = 0; i < R; i++) document.write(output[i], " " ) document.write( "</br>" ) return } // Recur for next row for (let i = 0; i < C; i++){ if (arr[m+1][i] != "" ) printUtil(arr, m+1, i, output) } } // A wrapper over printUtil function printf(arr){ // Create an array to store sentence let output = new Array(R).fill( "" ) // Consider all words for first row as starting // points and print all sentences for (let i = 0; i < C; i++){ if (arr[0][i] != "" ) printUtil(arr, 0, i, output) } } // Driver program let arr = [ [ "you" , "we" , "" ], [ "have" , "are" , "" ], [ "sleep" , "eat" , "drink" ]] printf(arr) // This code is contributed by shinjanpatra </script> |
you have sleep you have eat you have drink you are sleep you are eat you are drink we have sleep we have eat we have drink we are sleep we are eat we are drink
Time Complexity: O(n^m)
Where n is the number of words in the array and m is the number of rows.
Space Complexity: O(m)
Where m is the number of rows. We need an array of size m to store the output sentences.
Contact Us