Java Program to Compute all the permutations of the string

Introduction

Permutations of a string involve arranging all the characters of the string in all possible orders. This concept is widely used in computing problems related to anagrams, cryptography, and solving puzzles, along with applications in game theory and combinatorics. Calculating string permutations is often a key task in interviews and competitive programming.

In this article, you will learn how to compute all the permutations of a given string in Java using iterative and recursive approaches. Understand the methods through provided code examples and explanations to effectively harness the potential of these programming techniques.

Recursive Method to Find Permutations

Understand the Recursive Approach

1. Recognize that the recursive solution involves fixing one character and recursively solving for the rest of the string.
2. Swap the fixed character with each character in the string and solve recursively until the base case (typically when the string is one character).

Example Using Recursive Method

1. Implement the following function to generate and print all permutations recursively:

   java Copy

   public class Permutations {
       public static void permute(String str, int l, int r) {
           if (l == r)
               System.out.println(str);
           else {
               for (int i = l; i <= r; i++) {
                   str = swap(str, l, i);
                   permute(str, l + 1, r);
                   str = swap(str, l, i);
               }
           }
       }
   
       public static String swap(String a, int i, int j) {
           char temp;
           char[] charArray = a.toCharArray();
           temp = charArray[i];
           charArray[i] = charArray[j];
           charArray[j] = temp;
           return String.valueOf(charArray);
       }
   
       public static void main(String[] args) {
           String s = "ABC";
           permute(s, 0, s.length() - 1);
       }
   }
   

   In this code:

   • permute is the recursive method that swaps each character with its starting character and then calls itself with the next starting position.
   • swap changes the positions of two characters in a string.
   • The main method initiates permutation computation from the full string length.

Analyze the Recursive Flow

1. Pay attention to the way each character in the string is considered as a potential starting character.
2. Observe how after each recursive call, the string is reset to its original form before the next character swap for permutations.

Iterative Method Using Next Permutation Algorithm

Understanding the Iterative Approach

1. Grasp that this approach involves generating the next permutation lexicographically until all permutations are covered.
2. Use a specific sequence of swaps and reversions to generate the next higher permutation from the current one.

Example Using Iterative Method

1. Write the iterative function based on the next permutation algorithm:

   java Copy

   import java.util.Arrays;
   
   public class IterativePermutations {
       public static void allPermutations(char[] s) {
           Arrays.sort(s);
           System.out.println(String.valueOf(s));
           while (nextPermutation(s)) {
               System.out.println(String.valueOf(s));
           }
       }
   
       public static boolean nextPermutation(char[] array) {
           int k = array.length - 2;
           while (k >= 0 && array[k] >= array[k + 1]) {
               k--;
           }
           if (k == -1) {
               return false;
           }
           int l = array.length - 1;
           while (array[l] <= array[k]) {
               l--;
           }
           char temp = array[k];
           array[k] = array[l];
           array[l] = temp;
           reverse(array, k + 1, array.length - 1);
           return true;
       }
   
       public static void reverse(char[] array, int start, int end) {
           while (start < end) {
               char temp = array[start];
               array[start++] = array[end];
               array[end--] = temp;
           }
       }
   
       public static void main(String[] args) {
           char[] s = "BAC".toCharArray();
           allPermutations(s);
       }
   }
   

   This code outlines:

   • nextPermutation which steps to the next permutation.
   • reverse which reverses the part of the array.
   • allPermutations initially prints the smallest permutation and follows this with increasingly larger permutations.

Conclusion

Computing all permutations of a string in Java can be approached either recursively or iteratively, each having its scenarios and performance implications. By learning and implementing these two methods, you enhance your ability to tackle various problems in programming competitions and technical interviews effectively. Adapt these methods according to the problem's needs and constraints, which might dictate a preference for either of the approaches for efficiency.