Books
Browse Article Categories
User login
Featured Gallery Photo
Mountain view - off road
Active forum topics
Finding all possible combinations of a String using recursion using Java
String / Character combinations and recursion! Hmm..... Not that difficult compared to how it sounds. This Java tutorial gives you a quick introduction about recursion and combinations followed by a well explained working code for doing this in your Java program. Now lets get to the fun part and read this full Java tutorial...
Table of Contents [hide]
Before getting into the actual implementation lets quickly introduce the problem we are going to deal with.
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
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
Full Java Program
For the full Java source code listing and a download please go to the next page...
Comments
Well following must also be
Well following must also be counted possible combinations:
DBCA..etc
wrong algorithm
your algorithm produces duplicates. For instance 'CD' comes both from eliminating 'A' from 'ACD' and 'B' from 'BCD'.
Post new comment