Combination of all characters of a string

A very common questions and a fairly interesting exercise in programming is to develop and implement an algorithm which prints all the combinations of characters in a string, assuming that all the characters are distinct. eg. for input avi, the output should be a,v,i,av,ai,vi,avi.

Almost all of us are aware of the recursive algorithm for this problem and its implementation is also straight forward.
The recursive code which does the job.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void mycomb_ultrabad(char const * const s, int l, int *arr, int index, int start, int d)
{
	int i,j;
	if (index >= d)
		return ;
	for (j = start ; j < l ; j++)
	{
		arr[index] = j;
		if (index == d-1)
		{
			for (i=0;i<d;i++)putchar(s[arr[i]]);
			putchar('\n');
		}
		else
			mycomb_ultrabad(s,l,arr,index+1,j+1,d);
	}
	return ;
}


int main()
{
	int i,d;
	char s[100];
	scanf("%s",s);
	d = strlen(s);
	int arr[d+1];
	for (i=0;i<d;i++)
	{
		mycomb_ultrabad(s, d, arr,0,0,d-i);
	}
	return 0;
}

Also, all of us are very aware of the highly recursive nature of this code and hence the intriguing time it takes to complete even for a very small input. Knuth has given a very efficient algorithm in his epic TAOCP which does the job at a very high speed.
The (following) code which implements his algorithm and is very fast indeed.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>


void string_combinations(char * s, int d) {
	int n, j, x, *c;

	if (d <= 0) { puts(s); putchar('\n'); return; }
	if (d >= (n = strlen(s))) return;
	c = (int *)malloc((n + 2 - d)*sizeof(int));

	for(j = 0; j < n - d; ++j) c[j] = j;
	c[j + 1] = 0; x = n;
	do {
		c[j--] = x;
		for(x = 0; c[x] < n; ++x) { putchar(s[c[x]]); } putchar('\n');

		if (j >= 0) { x = j + 1; continue; }
		for(x = c[j = 0] + 1; x == c[j + 1]; x = c[++j] + 1) c[j] = j;
	} while (j < n - d);

	free(c);
}

int main()
{
	int i,d;
	char s[100];
	scanf("%s",s);
	d = strlen(s);
	int arr[d+1];
	for (i=0;i<d;i++)
	{
		string_combinations(s,d-i);
	}
	return 0;
}

When I was in first year at my college, and was introduced to programming, I was given this problem. I had no idea about recursion and the concept of algorithms because it was the first time I was studying computers. So, after some brain-storming I developed a method to solve the problem which did not use recursion (obviously because I didn’t even know what recursion was :P). The code which I had made then worked very fine and was very fast indeed. A few days back I was browsing through the codes I had made and I saw through that code. Well, keeping the algorithm same I implemented the code again, (now being a much better programmer than was then :D) and to my surprise my code beats the Knuth’s implementation by a considerable margin for all inputs. 😀 The following is the code which I recently made. Can you guess the algorithm ??? It was motivated from a very common real life analogy. Try to figure out how it works 🙂

#include<stdio.h>
#include<string.h>
#include<stdlib.h>


void mycomb_optimized(char const * const s, int d)
{
	d++;
	int l = strlen(s);
	int arr[d], j, k;
	for (j=0; j < d; j++) arr[j]=j;
	while ( j >=0  )
	{
		for (j=arr[d-1];j < l ; )
		{
			// print the existing string
			for (k=0;k<d;k++) putchar(s[arr[k]]);putchar('\n');
			arr[d-1] = ++j;
		}
		j = d - 2;k = 2;
		while (j >= 0)
		{
			if (arr[j] + 1 <= l - k )
			{
				arr[j]++;j++;
				break;
			}
			j--;k++;
		}
		while (j >= 0 && j <= d - 1 ) { 
			arr[j]=arr[j-1]+1;
			j++;
		}
	}
	return ;
}


int main()
{
	int i,d;
	char s[100];
	scanf("%s",s);
	d = strlen(s);
	int arr[d+1];
	for (i=0;i<d;i++)
	{
		mycomb_optimized(s, i);
	}
	return 0;
}

I still can’t believe how I could come up with such a nice method to solve the problem..

Advertisements

About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: