In this article, we will learn how to write a Java program to generate all possible permutations of strings in an array and store them in a new array. This is a great exercise for practicing recursion and backtracking in Java.
Problem statement:
We are given an array of strings, and the task is to generate all possible permutations of these strings and store them in a new array.
Approach to Solve the Problem
- Use Recursion:
- Use a recursive helper method to generate all permutations of the array.
- Backtracking:
- Swap elements to create permutations and backtrack to restore the original state.
- Collect Results:
- Store each generated permutation in a list.
- Convert to Array:
- Convert the list of permutations to an array for the final result.
Java program to generate all string permutations in an Array
Here is the Java program to solve the problem:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | package com.javacodepoint.stringarray; import java.util.ArrayList; import java.util.List; public class StringPermutations { public static void main(String[] args) { // Input array of strings String[] words = { "apple" , "banana" , "cherry" }; // Generate permutations List<String[]> permutations = generatePermutations(words); // Display the results System.out.println( "Permutations:" ); for (String[] permutation : permutations) { System.out.println(String.join( ", " , permutation)); } } // Method to generate all permutations of an array public static List<String[]> generatePermutations(String[] array) { List<String[]> result = new ArrayList<>(); permute(array, 0 , result); return result; } // Helper method for recursion and backtracking private static void permute(String[] array, int index, List<String[]> result) { if (index == array.length - 1 ) { // Add a copy of the array to the result list result.add(array.clone()); return ; } for ( int i = index; i < array.length; i++) { // Swap elements swap(array, index, i); // Recurse to generate permutations for the next index permute(array, index + 1 , result); // Backtrack: restore the original state swap(array, index, i); } } // Method to swap two elements in an array private static void swap(String[] array, int i, int j) { String temp = array[i]; array[i] = array[j]; array[j] = temp; } } |
OUTPUT:
Permutations:
apple, banana, cherry
apple, cherry, banana
banana, apple, cherry
banana, cherry, apple
cherry, banana, apple
cherry, apple, banana
Code Explanation:
- Input Array:
- The array
words
contains the strings for which permutations are to be generated.
- The array
- Recursive Method:
- The
permute
method generates all permutations by swapping elements and recursively calling itself for the next index.
- The
- Backtracking:
- After each recursive call, the
swap
method is used to restore the array to its original state.
- After each recursive call, the
- Store Results:
- Each generated permutation is cloned and added to the result list.
- Output Results:
- The program prints all generated permutations.
Conclusion
This program demonstrates an effective way to generate all permutations of strings in an array. It reinforces your understanding of recursion, backtracking, and array manipulation in Java. By practicing this program, you will enhance your problem-solving skills for complex scenarios involving permutations.
You can learn the Top 20 string array programs for interview preparation (Click here).