Question: Write an algorithm to print all possible combinations of characters in a string.
Answer: Any thoughts? One thing is for sure, we can definitely use some recursive logic here. Let’s approach this problem methodically. Since we need to generate combinations, we can start with a single character and then continue to add a character to combinations we have seen so far. Let’s use “abc” as an example.
Here’s some code in Java (for a change :)) to achieve what we’ve described above.
void combine(String instr, StringBuffer outstr, int index)
{
for (int i = index; i < instr.length(); i++)
{
outstr.append(instr.charAt(i));
System.out.println(outstr);
combine(instr, outstr, i + 1);
outstr.deleteCharAt(outstr.length() - 1);
}
}
combine("abc", new StringBuffer(), 0);
Have a better solution? Please let us know through the comments section.
int main()
{
char x[30];
printf(“\nEnter a word : “);
scanf(“%s”,x);
permutate(x,0,strlen(x)-1);
return 0;
}
void permutate(char *x,int i,int n)
{
int j;
if(i==n)
printf(“%s”,x);
else
{
for(j=i;j<=n;j++)
{
swap(x+i,x+j);
permutate(x,i+1,n);
swap(x+i,x+j);
}
}
}
void swap(char *x,char *y)
{
char temp;
temp=*x;
*x=*y;
*y=temp;
}
here is another solution…
Because there are n! possible combinations (permutations) of a string, any algorithm that claims to do it in less time is probably wrong.
Here’s a solution, in JavaScript-ish pseudocode (works in a language with mutable strings):
function anagrams(inStr) {
_anagrams(inStr, 0);
}
function _anagrams(inStr, fromIndex) {
var temp;
if (fromIndex == inStr.length) {
print(inStr);
} else {
for (var i = fromIndex; i < inStr.length; i++)
{
temp = inStr[fromIndex];
inStr[fromIndex] = inStr[i];
inStr[i] = temp;
_anagrams(inStr, fromIndex + 1);
inStr[i] = inStr[index];
inStr[fromIndex] = temp;
}
}
}
Here’s my implementation. I thought the original solution was not correct and it was not printing all the possible combinations of characters in string. This solution is O(n^2):
private void printCombinations(String string) {
for (int i = 0; i 0) {
substr = string.substring(0, i);
}
substr += string.substring(i + 1);
combine(substr,string.charAt(i));
}
}
private void combine(String instr, char first) {
String rotate = instr;
for (int i = 0; i < instr.length(); i++) {
System.out.println(first + rotate);
if (i < (instr.length() - 1)) {
rotate = instr.substring(i+1);
}
rotate += instr.substring(0, i+1);
}
}
Can some one give me the complexity of such an algorithm ?
Set getCombinations(String instr, StringBuffer outstr, int index)
{
Set combinations = new HashSet();
for (int i = index; i < instr.length(); i++)
{
outstr.append(instr.charAt(i));
combinations.add(outstr.toString());
combinations.addAll(getCombinations(instr, outstr, i + 1));
outstr.deleteCharAt(outstr.length() - 1);
}
return combinations;
}
I would recommend few improvement in the code to avoid invalid combinations (duplicates)
Set getCombinations(String instr, StringBuffer outstr, int index)
{
Set combinations = new HashSet();
for (int i = index; i < instr.length(); i++)
{
outstr.append(instr.charAt(i));
combinations.add(outstr.toString());
combinations.addAll(getCombinations(instr, outstr, i + 1));
outstr.deleteCharAt(outstr.length() – 1);
}
return combinations;
}
did you try running that code? it doesn’t print out quite a number of combinations (e.g. “cba”, “cab”, etc). What gives?
Other solution is multi the characters in each string with integer values and 256. Then sort the values and compare values next to each if any two numbers equals then corresponding strings are anagrams. O(n)+O(nlogn)+O(n)
Above algorithm generates repeats. Ex, input string is aaa