This Java code uses Depth-First Search (DFS) to generate all
possible combinations of a specific length (conbinationSize, which is set to 3)
from a given input string (input, set to "ABCDEF"). The combinations
are stored in a list called permutations.
Here's a breakdown of how the code works:
Key Concepts:
- Input
and Length: The input string is "ABCDEF", and the desired
combination length is 3. The code generates all combinations of 3
characters from this input.
- DFS
Approach:
ü
The code uses a recursive DFS approach to
generate the combinations.
ü
It maintains a boolean array isChoosed to track
which characters are already used in the current combination.
ü
The recursive method generateCombination builds
the combinations by adding one character at a time until the length matches conbinationSize.
- Backtracking:
ü
After adding a character to the current
combination, the algorithm proceeds to recursively build the next part.
ü
Once a combination is generated, it backtracks
by resetting the state (isChoosed[i] = false) and continues with other possible
characters.
DFS Class Overview:
Ø permutations:
List that holds all the generated combinations.
Ø input:
The input string to generate combinations from ("ABCDEF").
Ø conbinationSize:
The size of the combinations to generate (set to 3).
Ø isChoosed:
Boolean array to track if a character at index i has already been chosen for
the current combination.
Ø generateCombination(String
partialOutput): Recursive DFS method to generate combinations.
Ø printCombination():
Method to print all generated combinations.
Code Execution Flow:
- Initialize
DFS: An object of DFS is created in the main method.
- Generate
Combinations: The generateCombination("") method is called,
starting the DFS process with an empty string.
- Print
Results: Once the DFS completes, the generated combinations are
printed using printCombination().
Code:
java
|
package
com.kartik; import
java.util.ArrayList; import
java.util.List; /** * This class demonstrates DFS to generate
all combinations of a given input * with a specified length (combinationSize). * @author Kartik */ public class
DFS { /** * List of generated combinations */ List<String> permutations = new
ArrayList<String>(); /** * Input string used to generate
combinations */ String input = "ABCDEF"; /** * The length of the combinations */ int combinationSize = 3; /** * isChoosed[i] is true if the
combination that is currently prepared * contains input.charAt(i) */ boolean[] isChoosed = new
boolean[input.length()]; /** * The DFS method that will generate all
possible combinations. * @param partialOutput Current state of
the combination being built */ public void generateCombination(String
partialOutput) { // Base case: if the combination
reaches the desired length, add it to the list if (partialOutput.length() ==
combinationSize) { permutations.add(partialOutput); return; } // Recursive case: try adding each
unused character to the combination for (int i = 0; i <
input.length(); ++i) { if (!isChoosed[i]) { isChoosed[i] = true; // Mark
the character as used
generateCombination(partialOutput + input.charAt(i)); // Recursive
call isChoosed[i] = false; //
Backtrack } } } /** * Method to print all generated
combinations. */ void printCombination() { for (String c : permutations) { System.out.println(c); } } /** * Main method to execute the DFS
combination generation. */ public static void main(String[] args) { DFS dfs = new DFS();
dfs.generateCombination(""); // Start DFS with an empty
string dfs.printCombination(); // Print the
result } } |
Explanation of the DFS Approach:
- DFS:
ü
DFS is used to explore all possible combinations
by adding one character at a time.
ü
The recursion continues until the combination
length matches the desired size (combinationSize).
- Backtracking:
ü
After each recursive call, the algorithm
"backtracks" by resetting the state (isChoosed[i] = false).
ü
This allows other unused characters to be
considered in subsequent recursive calls.
- Efficiency:
ü
Since DFS explores all possible combinations,
the time complexity is proportional to the number of combinations, which is n!/(n−r)!n!
where n is the length of the input string and r is the combination length.
Sample Output:
For the input "ABCDEF" and combination size 3, the
program will generate and print combinations like:
Plain text
|
ABC |
You can modify combinationSize or input as needed to
generate combinations of different sizes or from different sets of characters.
0 Comments