A Combination of string could be described as the collection of the characters which it contains.
Unlike permutations, two combinations are considered to be the same if they contain the same characters, but may be in a different order. Give an algorithm that prints all possible combinations of the characters in a string. For example, “ac” and “ab” are different combinations from the input string “abc”, but “ab” is the same as “ba”.
The solution is achieved by generating n!/r! (n – r)! strings, each of length between 1 and n where n is the length of the given input string.
As, mathematically, to find r
combinations of the string with n
characters in given by nCr
.
So, if finding all the possible combination of the string we then have to go for
nC0 + nC1 + nC2 + ... + nCn
Also, from solving the above additon we have
nC0 + nC1 + nC2 + ... + nCn = 2n
That means the total number of combinations of the string would be 2n.
With this in mind you can represent each of the character within the string as a binary equivalent from 0 to 2n (exculding 2n, as we consider 0, as net there are 2n combinations).
For Example:
Take a String s = "ABC"
here n = 3,
So number of combinations are from zero (0) to 23 (ie, 8)
number | binary equivalent | String |
---|---|---|
0 | 000 | "" |
1 | 001 | "C" |
2 | 010 | "B" |
3 | 011 | "BC" |
4 | 100 | "A" |
5 | 101 | "AC" |
6 | 110 | "AB" |
7 | 111 | "ABC" |
Show me the Code
Here is the Code to do this.
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
public class CombinationOfString {
public static void main(String[] args) {
final Scanner sc = new Scanner(System.in);
System.out.println("Enter a String");
final String s = sc.next();
final List<String> combinations = new ArrayList<>();
findCombinations(s, 0, new StringBuilder(""), combinations);
System.out.println(combinations.stream().collect(Collectors.joining(" ")));
}
private static void findCombinations(String s, int startIndex, StringBuilder runner, List<String> combinations) {
for (int i = startIndex; i < s.length(); i++) {
// Add Character to end
runner.append(s.charAt(i));
// Save the combination
combinations.add(runner.toString());
// Take current info of runner and string and start from the next index
findCombinations(s, i+1, runner, combinations);
// Remove Character from the end
runner.setLength(runner.length() - 1);
}
}
}
Top comments (0)