String Permutations in an Array

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

  1. Use Recursion:
    • Use a recursive helper method to generate all permutations of the array.
  2. Backtracking:
    • Swap elements to create permutations and backtrack to restore the original state.
  3. Collect Results:
    • Store each generated permutation in a list.
  4. 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:

  1. Input Array:
    • The array words contains the strings for which permutations are to be generated.
  2. Recursive Method:
    • The permute method generates all permutations by swapping elements and recursively calling itself for the next index.
  3. Backtracking:
    • After each recursive call, the swap method is used to restore the array to its original state.
  4. Store Results:
    • Each generated permutation is cloned and added to the result list.
  5. 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).

Java logical programs list


Java Basic Programs

Java String Programs

Java String Array Programs

Java Miscellaneous Programs

Java Programs based on the Collection Framework

Leave a Reply

Your email address will not be published. Required fields are marked *