What is combination and how is it different from a permutation?
The mathematics' gurus would know this by heart, but I am going to refer to the Wikipedia for a proper definition.
"A combination is an un-ordered collection of unique sizes. (An ordered collection is called a permutation.)" from the Wikipedia article.
For example,
For a given String "ABCD",
a combination of un-ordered collection of unique sizes will be
[ABCD, BCD, ABD, ABC, ACD, AC, AD, AB, BC, BD, CD, D, A, B, C]
From my quick Google search, I also found out
"Number of ways of selecting zero or more things from ‘n’ different things is given by:- ( 2 ^ n - 1 ) "(from this article).
If we apply this formula in the above example, String "ABCD" with length of 4 should have ( 2 * 2 * 2 * 2 ) - 1 = 15 combinations.
This is exaclty what we are going to acheive in our code - Finding all possible combinations of characters from a given String. Note that for simplicity, we are going to assume that the input String (whose different combinations are going to be found) would not have any repetitive characters in it.
What is recursive programming?
Lets get a formal definition from Wikipedia:
"Creating a recursive procedure essentially requires defining a "base case", and then defining rules to break down more complex cases into the base case. Key to a recursive procedure is that with each recursive call, the problem domain must be reduced in such a way that eventually the base case is arrived at."
In very simple terms, a method calling itself again and again until a particular condition is met is called recursive programming.
Implementation:
The algorithm discussed below to solve this problem is chosen for its simplicity and ease of understanding. It may not be the most effective algorithm but it definitely solves this particular problem and is extremely simple.
Some points to note about this problem.
1. The given String itself is one of the combinations. For example, one of the combinations of the String "ABCD" is "ABCD" itself.
2. Every character in the String will be a combination. For example, for the String "ABCD" -- > "A", "B", "C", "D" will be some of the combinations.
Algorithm
To find the combinations of a String:
Step 1: Add the String to the combination results.
Step 2: If the String has just one character in it,
then stop the current line of execution.
Step 3: Create new sub-words from the String by removing one letter at a time.
If the String is "ABCD", form sub-words like "BCD", "ACD", "ABD", "ABC"
Step 4: For each of the sub-word, go to Step 1
import java.io.IOException;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
class StringCombinations
{
private Set combinations = new HashSet();
public StringCombinations(String sInputString)
{
generate(sInputString);
System.out.println("*** Generated " + combinations .size() + " combinations ***");
System.out.println(combinations);
}
public void generate(String word)
{
// Add this word to our combination results set
// System.out.println(word);
combinations.add(word);
// If the word has only one character we break the
// recursion
if (word.length() == 1)
{
combinations.add(word);
return;
}
// Go through every position of the word
for (int i = 0; i < word.length(); i++)
{
// Remove the character at the current position
// all call this method with that String (Recursion!)
generate(word.substring(0,i) + word.substring(i+1));
}
}
public static String readCommandLineInput(String inputMessage)
{
String inputLine ="abcd";
return inputLine;
}
public static void main(String args[])
{
// Request and read user input
String sInstruction = "Enter a String: \n";
String sInputString = readCommandLineInput(sInstruction);
new StringCombinations(sInputString);
}
}// End of StringCombinations
Run Here https://ideone.com/EPV9i
Another Informative Link http://www.codeguru.com/cpp/cpp/algorithms/combinations/article.php/c5117
