NicholasAdamou

Problem 3: Print all possible strings of length k

Sep 13th, 2019
384
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.85 KB | None | 0 0
  1. public class Main {
  2.     // Given a string of alphabets and a number k, write a function to print all of the combinations of length k of these alphabets.
  3.     // The string does not contain duplicate alphabets.
  4.     // EXPECTED OUTPUT: abd, abs, abe, ads, ade, ase, bds, bde, bse, dse.
  5.     public static void main(String[] args) {
  6.         char[] alphabet = { 'a', 'b', 'd', 's', 'e' };
  7.         int k = 3; // length of output string.
  8.  
  9.         System.out.println("EXPECTED OUTPUT: abd, abs, abe, ads, ade, ase, bds, bde, bse, dse");
  10.         System.out.print("ACTUAL OUTPUT: ");
  11.         printAllCombinations(alphabet, k);
  12.     }
  13.  
  14.     // Base function used to call the recursive version of itself with given alphabet and length, k.
  15.     private static void printAllCombinations(char[] alphabet, int k) {
  16.         // Initially set the prefix to "" and n to 0, while passing alphabet and length, k to printAllCombinations.
  17.         printAllCombinations(alphabet, "", 0, k);
  18.     }
  19.  
  20.     // Recursive method used to print all possible strings of length k, given a set of characters.
  21.     // However, use n to keep track of your current location in the array alphabets.
  22.     private static void printAllCombinations(char[] alphabet, String prefix, int n, int k) {
  23.         // Base case: k is 0,
  24.         // print prefix.
  25.         if (k == 0) {
  26.             // Only print ', ' if n is less than the length of the current prefix.
  27.             if (n > prefix.length()) {
  28.                 System.out.print(", ");
  29.             }
  30.  
  31.             System.out.print(prefix);
  32.             return;
  33.         }
  34.  
  35.         // One by one add all characters
  36.         // from set and recursively
  37.         // call for k equals to k - 1.
  38.         // However, loop only from n to length of the alphabet.
  39.         for (int i = n; i < alphabet.length; i++) {
  40.             // Next character of input added.
  41.             String newPrefix = prefix + alphabet[i];
  42.  
  43.             // k is decreased and n is increased, because
  44.             // we have added a new character.
  45.             printAllCombinations(alphabet, newPrefix, i + 1, k - 1);
  46.         }
  47.     }
  48. }
Advertisement
Add Comment
Please, Sign In to add comment