Print all permutation of a string using ArrayList
Given a string str, the task is to print all the permutations of str.
A permutation is an arrangement of all or part of a set of objects, with regard to the order of the arrangement.
For instance, the words ‘bat’ and ‘tab’ represents two distinct permutation (or arrangements) of a similar three-letter word.
Examples:
Input: str = “abc”
Output: abc acb bac bca cba cabInput: str = “bat”
Output: bat bta abt atb tba tab
Approach: Write a recursive function that will generate all the permutations of the string. Terminating condition will be when the passed string is empty, in that case the function will return an empty ArrayList.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> // includes all standard libraries in one header using namespace std; // Utility function to print the contents // of the vector void printVector(vector<string> arrV) { arrV.erase( remove (arrV.begin(), arrV.end(), "" ), arrV.end()); for ( int i = 0; i < arrV.size(); i++) cout << arrV[i] << " " ; } // Function to returns the vector which contains // all the permutation of str vector<string> getPermutation(string str) { // If string is empty if (str.length() == 0) { // Return an empty vector vector<string> empty; empty.push_back( "" ); return empty; } // Take first character of str char ch = str[0]; // Take sub-string starting from the // second character string subStr = str.substr(1); // Recursive call vector<string> prevResult = getPermutation(subStr); // Store the generated permutations // into the resultant vector vector<string> Res; for (string val : prevResult) { for ( int i = 0; i <= val.length(); i++) { Res.push_back(val.substr(0, i) + ch + val.substr(i)); } } // Return the resultant vector return Res; } // Driver code int main() { string str = "abc" ; printVector(getPermutation(str)); return 0; } |
Java
// Java implementation of the approach import java.util.ArrayList; public class GFG { // Utility function to print the contents // of the ArrayList static void printArrayList(ArrayList<String> arrL) { arrL.remove( "" ); for ( int i = 0 ; i < arrL.size(); i++) System.out.print(arrL.get(i) + " " ); } // Function to returns the arraylist which contains // all the permutation of str public static ArrayList<String> getPermutation(String str) { // If string is empty if (str.length() == 0 ) { // Return an empty arraylist ArrayList<String> empty = new ArrayList<>(); empty.add( "" ); return empty; } // Take first character of str char ch = str.charAt( 0 ); // Take sub-string starting from the // second character String subStr = str.substring( 1 ); // Recursive call ArrayList<String> prevResult = getPermutation(subStr); // Store the generated permutations // into the resultant arraylist ArrayList<String> Res = new ArrayList<>(); for (String val : prevResult) { for ( int i = 0 ; i <= val.length(); i++) { Res.add(val.substring( 0 , i) + ch + val.substring(i)); } } // Return the resultant arraylist return Res; } // Driver code public static void main(String[] args) { String str = "abc" ; printArrayList(getPermutation(str)); } } |
Python3
from typing import List # Function to returns the list which contains all the permutations of a string def get_permutation(string: str ) - > List [ str ]: # If string is empty if len (string) = = 0 : # Return an empty list return [""] # Take first character of str ch = string[ 0 ] # Take sub-string starting from the second character sub_str = string[ 1 :] # Recursive call prev_result = get_permutation(sub_str) # Store the generated permutations into the resultant list res = [] for val in prev_result: for i in range ( len (val) + 1 ): res.append(val[:i] + ch + val[i:]) # Return the resultant list return res # Driver code def main(): string = "abc" print (get_permutation(string)) if __name__ = = "__main__" : main() # This code is contributed by mallelagowtalm. |
C#
// C# implementation of the approach using System.Collections.Generic; using System; class GFG { // Utility function to print the contents // of the ArrayList static void printArrayList(List<String> arrL) { arrL.Remove( "" ); for ( int i = 0; i < arrL.Count; i++) Console.Write(arrL[i] + " " ); } // Function to returns the arraylist which contains // all the permutation of str public static List<String> getPermutation(String str) { // If string is empty if (str.Length == 0) { // Return an empty arraylist List<String> empty = new List<String>(); empty.Add( "" ); return empty; } // Take first character of str char ch = str[0]; // Take sub-string starting from the // second character String subStr = str.Substring(1); // Recursive call List<String> prevResult = getPermutation(subStr); // Store the generated permutations // into the resultant arraylist List<String> Res = new List<String>(); foreach (String val in prevResult) { for ( int i = 0; i <= val.Length; i++) { Res.Add(val.Substring(0, i) + ch + val.Substring(i)); } } // Return the resultant arraylist return Res; } // Driver code public static void Main(String[] args) { String str = "abc" ; printArrayList(getPermutation(str)); } } // This code has been contributed by 29AjayKumar |
Javascript
<script> // JavaScript implementation of the approach // Utility function to print the contents // of the ArrayList function printArrayList(arrL) { for (let i = 0; i < arrL.length; i++) document.write(arrL[i] + " " ); } // Function to returns the arraylist which contains // all the permutation of str function getPermutation(str) { // If string is empty if (str.length == 0) { // Return an empty arraylist let empty = []; empty.push( "" ); return empty; } // Take first character of str let ch = str[0]; // Take sub-string starting from the // second character let subStr = str.substring(1); // Recursive call let prevResult = getPermutation(subStr); // Store the generated permutations // into the resultant arraylist let Res = []; for (let val of prevResult) { for (let i = 0; i <= val.length; i++) { Res.push(val.substring(0, i) + ch + val.substring(i)); } } // Return the resultant arraylist return Res; } // Driver code let str = "abc" ; printArrayList(getPermutation(str)); // This code is contributed by unknown2108 </script> |
Output
abc bac bca acb cab cba
Time Complexity: O(n*n!)
Auxiliary Space: O(n)
Contact Us